Arrays & Hashing

How to recognize it

Arrays-and-hashing questions almost always contain one of a few tells: "have you seen this value before," "how many times does X appear," "find two elements that add up to," or "group these by some shared property." The common thread is a lookup that would otherwise require rescanning the array — and a hash map turns that rescan into a single lookup.

A useful test while reading the prompt: if your first instinct is a nested loop comparing every pair of elements, stop and ask what you'd need to remember about elements you've already visited to avoid the second loop entirely. That thing you need to remember is almost always the hash map's value.

How the pattern works

The classic example is finding two numbers in an array that sum to a target. The brute force checks every pair — O(n²). The hash-map version walks the array once, and at each element checks whether "target minus this element" has already been seen. If it has, you're done; if not, record the current element and move on. One pass, one lookup per element, O(n) total.

def two_sum(nums, target):
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

function twoSum(nums, target) {
  const seen = new Map(); // value -> index
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) {
      return [seen.get(complement), i];
    }
    seen.set(nums[i], i);
  }
  return [];
}

Say the design decision before you type it: "I'll map each number to its index as I go, so I can check for the complement in constant time." That one sentence is worth more to an interviewer than the code itself — see Thinking Out Loud for why.

Common mistakes

• Writing the nested-loop brute force fully before mentioning a hash map is even possible — say the O(n) idea first, then decide together whether to code the brute force as a stepping stone
• Forgetting that dictionary/map keys must be hashable — this bites candidates on problems using lists or arrays as keys in Python, or accidentally using object reference equality in JavaScript
• Not clarifying duplicate handling upfront (can the same element be used twice, are there duplicate values in the array) — this changes whether you check-then-insert or insert-then-check
• Reaching for a hash map when the array is already sorted and two pointers would use less space — see Two Pointers below

Complexity

Most arrays-and-hashing solutions are O(n) time and O(n) space — you trade memory for avoiding a second pass. State both numbers explicitly and be ready for the follow-up "can you do it with O(1) space instead" — the honest answer is usually no, not without sorting first and changing the approach to two pointers, which costs you the O(n) time. Naming that trade-off is itself the signal interviewers are listening for. For the general skill of stating and defending complexity, see Time & Space Complexity.