Hash maps and counting
Trade memory for time: remember what you have seen so the inner loop becomes a lookup.
Two Sum. Given an array nums and a target, return the indices of the two numbers that add up to target. Exactly one answer exists; do not use the same element twice.
Signals that point here
- "Find a pair / complement / duplicate" in an unsorted array.
- You are about to write a nested loop whose inner loop searches for something.
- Counting: anagrams, frequencies, "first unique", majority element.
- Grouping by a computed key (sorted letters, a tuple of counts).
The idea
The brute force checks every pair, O(n²). But for each x the partner is fully determined: target - x. A hash map of values already seen answers "have I met the partner?" in O(1) on average.
The invariant: when you stand at index i, seen holds every value to the left of i. Checking before inserting is what stops an element pairing with itself.
def two_sum(nums: list[int], target: int) -> list[int]:
seen: dict[int, int] = {} # value -> index
for i, x in enumerate(nums):
if target - x in seen:
return [seen[target - x], i]
seen[x] = i # insert AFTER the check
return []public static class Hashing
{
public static int[] TwoSum(int[] nums, int target)
{
var seen = new Dictionary<int, int>(); // value -> index
for (int i = 0; i < nums.Length; i++)
{
if (seen.TryGetValue(target - nums[i], out int j))
return new[] { j, i };
seen[nums[i]] = i; // insert AFTER the check
}
return Array.Empty<int>();
}
}Complexity
O(n) time on average, O(n) extra space. Worst-case hashing is O(n) per operation, which is worth one sentence if the interviewer asks about adversarial input.
Pitfalls interviewers watch for
- Inserting before checking, so
[3]with target6pairs the element with itself. - Storing value -> index when values repeat and you need the first index: decide which one the problem wants.
- Using a list for
seen(inon a list isO(n)). - Forgetting the no-answer return path.
Variants worth knowing
- Count pairs instead of returning one: add
count[target - x]to a running total, then incrementcount[x]. - Group anagrams: key each word by
''.join(sorted(w))or a 26-tuple of counts. - If the array is sorted, two pointers solve it in
O(1)space (next lesson).
Test it like the interviewer will
two_sum([2, 7, 11, 15], 9)returns[0, 1]two_sum([3, 2, 4], 6)returns[1, 2]two_sum([3, 3], 6)returns[0, 1]two_sum([1, 2], 7)returns[]- Say the cases out loud before you run them. OpenAI's published guide names test coverage as part of the bar; see Sources.
Step through it: two_sum([3, 8, 4, 11, 6], 10)
Each step is recorded from an instrumented copy of the Python above, run when the site was built.
Practice
Written for this site to drill the lesson. Not reported interview questions.
- Return all unique pairs that sum to target, with duplicates in the input.
- Find the length of the longest run of consecutive integers in an unsorted array in
O(n). - Given a list of words, group the anagrams together.
Check yourself
Why check before inserting?
So an element cannot pair with itself; seen must hold only indices strictly to the left.
What does the hash map buy, and what does it cost?
Turns the inner search from O(n) into average O(1), for O(n) extra memory.