Hash Map & Sets

This is the most common trick in interview problems and the easiest one to under-use. If a brute force needs to ask “have I seen this before?” or “how many times?”, a hash map answers in constant time and collapses a nested loop into a single pass.

Why it works#

A hash map computes a number from your key and uses it to jump straight to a slot. It does not search. That is the whole idea, and it is why lookup does not get slower as the map grows: the cost of finding a key is roughly the cost of hashing it.

The trade is explicit. You spend O(n) memory to avoid O(n) work per element. In an interview that is almost always the right trade, and saying so out loud — “I’ll trade some space to drop this to linear” — is often the answer they are listening for.

Two operations cover nearly everything:

• A set answers is this present?
• A map answers what is associated with this? — an index, a count, a group.

The complement trick#

The classic case is Two Sum. The brute force compares every pair, which is O(n²). But for any element you are looking at, there is exactly one value that would complete the pair — target − nums[i] — and you already know it. So instead of searching forward for it, check whether you have already walked past it.

Two details make this work. You look up the complement before inserting the current element, which stops a value from pairing with itself. And you only ever move forward: the map is the memory of everything behind you, so there is never a reason to look back.

seen = empty map          // value -> index

for i = 0 .. n - 1:
    need = target - nums[i]

    if need in seen:
        return (seen[need], i)     // look up before inserting

    seen[nums[i]] = i

return none

One pass, O(n) time, O(n) space. Note it does not need sorted input — this is the tool to reach for when the two-pointer approach is unavailable because sorting would destroy the indices you were asked to return.

Counting#

Swap the value for a tally and the same structure answers a different family of questions: are these two strings anagrams, can this note be built from that magazine, which element appears most often, how long a palindrome can these letters make.

count = empty map         // item -> how many times seen

for item in items:
    count[item] = count[item] + 1     // missing keys start at 0

The skill is in what you do with the tally afterwards. Two strings are anagrams when their counts match exactly. A ransom note is possible when every count it needs is available. A palindrome can use every letter that appears an even number of times, plus one odd letter in the middle — which is a counting question wearing a disguise.

Membership#

When you only care whether something is present, use a set. It is the same structure with the values thrown away, and the intent is clearer to whoever reads the code.

seen = empty set

for item in items:
    if item in seen:
        return true       // duplicate found
    add item to seen

return false

Choosing the key#

This is the part that actually takes skill. The structure is trivial; deciding what to key on is the problem.

• The value itself — duplicates, membership.
• A normalised form of the value — sort a word’s letters and every anagram of it collapses to the same key, which is how you group anagrams in one pass.
• A running total — key a prefix sum and you can find subarrays summing to a target, because two equal prefix sums mean the stretch between them sums to zero.
• The thing you still need — the complement, above. Keying on what is missing rather than what you have is the move people find least obvious.

If a problem feels like it wants a hash map but you cannot see the key, that is the question to sit with. It is rarely the data structure that is missing.

What it costs#

Worth knowing before you claim O(1) in an interview:

• Lookups are O(1) on average, not in the worst case. Adversarial keys can collide into one bucket and degrade to O(n). It almost never matters in practice; saying “O(1) average” shows you know it.
• Hash maps do not preserve order. If the answer depends on ordering, you need something else, or you need to sort at the end.
• Keys must be hashable and compared by value. In most languages that rules out mutable types as keys, and it is why a list usually has to become a tuple or a string first.
• Counting a fixed, small alphabet — the 26 lowercase letters, say — is often better served by a plain array of 26 slots. Same idea, no hashing, and a smaller constant factor.

Recognising it#

Reach for a hash map or set when:

• The brute force is a nested loop whose inner pass is only asking have I seen this or how many of these are there.
• The problem mentions duplicates, frequencies, anagrams, or grouping.
• You need to return original indices, so sorting is off the table.
• You can describe the answer as “for each element, something about the elements before it”. That sentence is a hash map almost every time.

Summary#

One structure, two uses: a set remembers what, a map remembers what and how much. The mechanics are the easy part — constant-time lookup that turns a second loop into a single pass. The judgement is entirely in the key. Pick the right thing to key on and most of these problems collapse into a few lines; pick the wrong one and the map does not help at all.