Two Sum: from brute force to a one-pass hash map
What interviewers are testing
Two Sum is the standard opening coding question because almost everyone can write the brute force, yet far fewer can derive the one-pass hash map and justify the switch. Interviewers watch how you reframe the problem from comparing pairs to querying for a complement, whether you keep the scan single-pass, and whether you can state the space-time trade-off without prompting. The follow-ups reveal whether you noticed the duplicate-value trap and can adapt the same idea to sorted input and to Three Sum.
Mental model
For each element the partner you need is fully determined: complement = target - nums[i]. Instead of scanning the rest of the array for that partner, remember every value already visited in a hash map keyed by value. If the complement is in the map, its index and the current index are the answer; otherwise store the current value and move on. One pass, average O(n) time, O(n) extra space.
Step-by-step solution
Step 1 of 5
Brute force checks every pair
Start with the honest solution so the improvement has something to beat. For each index i, scan every j greater than i and test whether nums[i] + nums[j] equals the target. The animation follows the loops on nums = [3, 2, 4, 3] with target 6: the first two probes miss, and the third finds 3 + 3. Every element is compared with every later element, so the work is (n-1) + (n-2) + ... + 1 = n(n-1)/2 comparisons, which is O(n²) time and O(1) extra space. On a ten-thousand-element array that is roughly fifty million additions, all to find a pair that a single organized pass could locate with ten thousand lookups. The brute force is the right baseline to say out loud: it proves you can solve the problem and isolates exactly what the faster solution must remove, namely the repeated rescanning.
Animation — Brute force checks every pair
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 [];}Variables
i = 0, j = 1: 3 + 2 = 5 misses the target 6.
Edge cases & traps
- Duplicate values such as [3, 3] with target 6: check the map before inserting, or index 0 finds itself and returns [1, 1] instead of [0, 1].
- No valid pair: the loop should exit and return an empty array, but some variants guarantee exactly one solution - state the contract before coding.
- Negative values and zeros are safe: complement = target - nums[i] needs no special casing; absolute-value heuristics break them.
- Integer overflow in fixed-width languages: target - nums[i] can cross the integer bounds even when the final answer is valid - use 64-bit arithmetic or reorder the comparison.
- Huge duplicate runs overwrite one map entry per value: since the check happens first, you still get the most recent compatible partner, which satisfies any-valid-pair contracts.