Two Sum: The Hash Map Pattern Every Interview Builds On
The one-pass hash map solution to Two Sum, explained step by step — intuition, a worked walkthrough, JavaScript code, complexity analysis, and common mistakes.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Two Sum is the first problem most people ever open on LeetCode, and it earns that spot. Hidden inside a deceptively simple prompt — find two numbers that add up to a target — is the single most reusable idea in interview prep: trade memory for time by remembering what you've already seen. Master the reasoning here and you've unlocked the approach behind dozens of harder problems, from Subarray Sum Equals K to Longest Consecutive Sequence.
The problem
Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. Each input has exactly one solution, and you may not use the same element twice.
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1] // because nums[0] + nums[1] === 9Two details in that statement quietly shape the solution:
- You must return indices, not values — so whatever you store has to remember positions.
- Exactly one valid pair exists — so the moment you find it, you can return immediately.
The brute force baseline
The obvious approach checks every pair: for each element, scan the rest of the array for its partner.
function twoSum(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) return [i, j];
}
}
return [];
}This works, but it re-answers the same question over and over. When the outer loop sits at index i, the inner loop asks: "is the number I need anywhere to the right?" — a full O(n) scan, repeated n times, for O(n²) total. On a 10⁵-element array that's ten billion comparisons. Interviewers expect you to state this baseline in one breath and then beat it.
The key insight: ask for the complement
Flip the question. Instead of searching forward for a partner, ask as you walk: "have I already seen the number that completes me?"
For each value x, the partner it needs is fixed and computable in O(1):
complement = target - xA hash map gives O(1) membership checks. So keep a map of value → index for everything you've walked past. At each element, one lookup answers the partner question instantly — no rescanning.
This is the "have I seen it before?" pattern: a single pass, where a hash structure replaces the inner loop entirely.
The one-pass solution
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 []; // unreachable when exactly one solution exists
}Note the order inside the loop: check first, then store. Checking before storing means the current element can never match itself, which handles cases like target = 6 with a single 3 in the map correctly.
Walkthrough: nums = [3, 2, 4], target = 6
| Step | i | nums[i] | complement | seen (value → index) | Action |
|---|---|---|---|---|---|
| 1 | 0 | 3 | 3 | {} | 3 not in map → store {3: 0} |
| 2 | 1 | 2 | 4 | {3: 0} | 4 not in map → store {2: 1} |
| 3 | 2 | 4 | 2 | {3: 0, 2: 1} | 2 is in map → return [1, 2] |
Step 1 is the subtle one: the complement of the first 3 is also 3, but the map is still empty, so nothing matches. If you stored before checking, the element would find itself and return [0, 0] — wrong. This exact trap is why the check-then-store order matters.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force | O(n²) | O(1) | n scans of up to n elements |
| Sort + two pointers | O(n log n) | O(n) | sorting dominates; must track original indices |
| One-pass hash map | O(n) | O(n) | one lookup + one insert per element |
The hash map version does a single pass with constant work per element. The space cost is the map itself — up to n entries when the answer pair sits at the very end.
Common mistakes
- Storing before checking. As shown in the walkthrough, this lets an element pair with itself when
nums[i] * 2 === target. - Returning values instead of indices. The problem asks for positions; storing
value → index(not the reverse) is what makes this possible. - Sorting when indices matter. Sorting destroys the original positions. The two-pointer variant only fits sorted-input versions of the problem, like Two Sum II.
- Worrying about duplicate keys. If
nums = [3, 3]andtarget = 6, the second3finds the first one in the map before overwriting anything. Exactly-one-solution inputs make overwrites harmless.
Where this pattern shows up next
The complement-lookup trick generalizes far beyond one problem:
- Two Sum II - Input Array Is Sorted — the sorted variant where two pointers beat the hash map on space.
- Contains Duplicate — the same "have I seen it?" question in its purest form.
- Longest Consecutive Sequence — set membership powering an O(n) answer that looks impossible at first.
- Top K Frequent Elements — hash map counting as the setup for a heap-based ranking.
You can also step through Two Sum interactively to watch the map fill up and the complement check fire, one element at a time.
FAQ
Why does Two Sum use a hash map instead of sorting?
Because the answer requires original indices, and sorting destroys them. A hash map finds each element's complement in O(1) while preserving positions, giving O(n) total time. Sorting first costs O(n log n) and forces you to track where each value originally lived.
What is the time complexity of the optimal Two Sum solution?
O(n) time and O(n) space. The array is scanned once, and each element does one O(1) average-case map lookup and one insert. The brute-force nested-loop approach is O(n²) time with O(1) space.
Does the one-pass solution handle duplicate numbers?
Yes. Because each element checks the map before inserting itself, a duplicate like the second 3 in [3, 3] with target 6 finds the first 3 already stored and returns both indices. No special-casing is needed.
When should I use two pointers instead of a hash map?
When the input is already sorted (or you're allowed to sort it because values, not indices, are the answer). Two pointers on a sorted array solve the pair-sum question in O(n) time with O(1) extra space — that's the intended solution for Two Sum II.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.