Hash Maps and Sets

1The mental model (what this really is)#

A hash map is a box of labeled drawers. Hand it a key, it finds the drawer instantly, you read or write the value inside. No scanning, no sorting, no walking the whole thing.

• A map answers: "do I have this, and what is next to it?"
• A set is the same machine with the values ripped out. It only remembers keys and answers one question: "have I seen this before?"

The superpower is the speed.

• Lookup, insert, and delete all cost O(1) on average.
• Compare that to an array, where finding something means scanning every element: O(n) per search.
• Replace a scan inside a loop with a lookup and an O(n squared) solution collapses into O(n).
• On an array of 100,000 elements that is the difference between roughly 10 billion operations and 100,000.

Two mental shifts make it click.

• You are trading memory for speed. Spend up to O(n) extra space to remember what you have seen so you never look twice.
• You often store more than a raw yes or no. The value can be a count, an index, the last position you saw something, or a list.

2How to recognize it (the signals in a problem)#

You will never get a problem that says "use a hash map." You get a story. These are the signals the story is really hashing:

• It says "find duplicates," "all unique," or "has it appeared before."
• You need to count how many times things occur. Frequencies scream hash map.
• You catch yourself writing a nested loop whose inner loop searches for a matching value. That inner search is a lookup in disguise.
• You need to pair things up: "does the complement exist," "do two things map to each other," "group these by some key."
• Membership asked many times: "is x in this collection."
• Anything about anagrams, which are just letter counts.

3The template (how it works, with pseudocode)#

Almost every hashing solution is one pass that builds a structure and checks it as it goes. The shape is always close to this:

seen = empty hash map   # or an empty set

for item in input:
    # 1. CHECK before you store
    if (something about item) is already in seen:
        do the thing (return answer, update result, skip, etc.)

    # 2. STORE this item so future items can find it
    seen[key(item)] = value(item)

return result

Order matters more than people realize: check first, then store.

• Store before you check and you can match an element against itself and get a wrong answer.
• This single ordering bug is the most common reason a Two Sum style solution passes the sample and fails a hidden case.

For a pure counting problem the template is even simpler:

count = empty hash map with default 0

for item in input:
    count[item] += 1

# now count holds every frequency, do whatever you need

The three decisions you make every time:

1. What is the key? The thing you look up by. An element, a sorted word, a (row, col) pair, a running sum.
2. What is the value? A boolean, a count, an index, a list of indices. This choice is the whole solution.
3. Set or map? If you only need "seen it or not," use a set. If you need any extra info, use a map.

Say these three answers out loud before you write a line. Interviewers grade the fact that you decided on purpose, not by accident.

4A worked example (walk through one problem step by step)#

The classic this pattern is famous for: Two Sum. Given an array of numbers and a target, return the indices of the two numbers that add up to the target.

The brute force, and why it is not enough.

• For every number, loop through the rest and check if any pair sums to the target.
• Two nested loops: O(n squared) time, O(1) space.
• On a long array that is the answer that gets you a polite "can you do better."

Now think with the hash map lens.

• For each number x, the partner I need is exactly target - x. Call it the complement.
• So the real question at every step is: "have I already seen the complement?"
• Membership question means hash.

The plan.

• Walk the array once.
• For each number, first ask whether its complement is already in my map.
• If yes, I found the pair. If no, record the current number and its index so a future number can find it.
• I store the number as the key and the index as the value, because the problem wants indices back.

seen = empty map   # number -> its index

for i, x in enumerate(nums):
    need = target - x
    if need in seen:
        return [seen[need], i]
    seen[x] = i

Run it on nums = [2, 7, 11, 15], target = 9.

• i=0, x=2. I need 9 minus 2, which is 7. Is 7 in my map? Empty, so no. Store 2 -> 0.
• i=1, x=7. I need 9 minus 7, which is 2. Is 2 in my map? Yes, stored at index 0. Return [0, 1]. Done.

What just happened.

• One pass. Two iterations on this input, and I never touch index 2 or 3.
• Checking before storing avoids using the same element twice: if the target were 4 and the array had a single 2, checking first means I never pair that 2 with itself. I only match it against a 2 that came earlier.
• A nested-loop search became a single pass by remembering what I saw: O(n squared) time down to O(n) time, at the cost of O(n) space.
• You reuse this exact shape in dozens of problems, from Contains Duplicate to Subarray Sum Equals K.

5Variations and gotchas#

Map vs set.

• Use a set when the answer is pure yes or no. "Does this array contain a duplicate" is a set problem.
• The moment you need an index, a count, or any payload, upgrade to a map.

Value as a count.

• Counting frequencies is maybe half of all hashing problems: anagram checks, majority element, finding the character that appears once.
• Build the count map, then read it.
• For lowercase-letter problems you can swap the map for a fixed size 26 array, which is a tighter constant and a nice thing to mention.

Value as a list.

• When many keys collapse to the same bucket, store a list.
• Grouping anagrams works by using the sorted word as the key and appending each original word to the list under that key.
• Sorting each word costs O(L log L), so the whole thing is O(n times L log L) for n words of length L.

Composite keys.

• The key does not have to be a single value. It can be a pair, a tuple, or a string you build on the fly.
• Group by (row / 3, col / 3) to find a sudoku box, or use a comma-joined string of coordinates.
• If a language cannot hash a raw pair, turn it into a string or a tuple.

The prefix-sum map (a sharper variation).

• To count subarrays that sum to a target k, store running sums you have seen and how often.
• At each index, ask whether runningSum - k has appeared before.
• This turns a quadratic subarray scan into one O(n) pass.
• It feels like magic the first time, so practice it on purpose until the complement idea maps cleanly from Two Sum.

Set for sequence tricks.

• Longest-consecutive-sequence drops everything into a set, then only starts counting a run from numbers that have no left neighbor in the set.
• That "only start if x minus 1 is absent" constraint keeps the whole thing O(n) instead of O(n log n) from sorting.

6Complexity#

Average case, the operations you care about are all O(1):

• Insert: O(1)
• Lookup: O(1)
• Delete: O(1)

What that gives you.

• A single pass over n items doing constant work each step is O(n) time. That is the number you quote.
• Space is O(k) where k is the number of distinct keys you store, which is O(n) in the worst case.
• You are buying that speed with memory. Say the trade out loud, because the trade is the point, not an afterthought.

7Mistakes that cost people the round#

• Reaching for the nested loop and never looking back. The brute force often works and passes small tests, so people stop there. The interviewer wanted the O(n) version. Train yourself to see the hidden lookup.
• Storing before checking. The single most common bug in Two Sum style problems. It makes an element match itself. Check, then store.
• Choosing the wrong value type. Using a set when you needed the index, then rewriting under time pressure with five minutes left. Decide key and value before you type.
• Over-engineering the key. Building giant string keys when a simple tuple works, or sorting when a frequency count is enough. Keep the key as small and cheap as the problem allows.
• Not stating the trade-off. You solved it in O(n). If you do not say "I am using O(n) extra space to get there," a sharp interviewer wonders if you understand what you did. Narrate it.
• Forgetting edge cases. Empty input, a single element, duplicates, negative numbers, and whether a number can pair with itself. Hashing problems love these, and a missed empty-input check is a cheap way to lose points.

8Your practice path (named problems by difficulty)#

Do them in this order. Each one adds exactly one new idea on top of the last.

Warm up (pure recognition):

• Contains Duplicate
• Two Sum
• Valid Anagram
• Intersection of Two Arrays
• First Unique Character in a String
• Majority Element

Build the core skill (counting and grouping):

• Group Anagrams
• Top K Frequent Elements
• Valid Sudoku
• Isomorphic Strings
• Ransom Note

Level up (the clever variations):

• Longest Consecutive Sequence
• Subarray Sum Equals K
• Longest Substring Without Repeating Characters
• 4Sum II
• Continuous Subarray Sum

Solve the first group cold in under 10 minutes each and explain the prefix-sum trick in Subarray Sum Equals K without notes, and you are in good shape for any easy-to-medium hashing question.

9Where this shows up#

Hashing is the bread and butter of phone screens and the first 15 minutes of onsites everywhere.

• Amazon leans on frequency counting and Two Sum variants constantly, often as the warmup before a two-pointer or BFS follow-up.
• Google likes the sharper versions, prefix sums and consecutive sequences, as warmups before a harder follow-up in the same 45-minute slot.
• Meta uses it for string and array screens, where Group Anagrams and Subarray Sum Equals K show up again and again.
• Startups use it because it is quick to pose and quick to grade on a 30-minute call.

It also hides inside bigger problems.

• Sliding window keeps a count map.
• Graph traversal keeps a visited set.
• Dynamic programming memoizes with a map.
• LRU cache is a hash map glued to a linked list.
• Learn hashing well and you have paid down a debt you would owe in half the other patterns too.

The moment you write a loop inside a loop to answer "is this value in that list," you have already found your hash map.

Want to see which rounds and companies lean hardest on this pattern? Check the company guides to match it to real interview loops.