DSAWiser blog
How to trace a Two Sum solution
Walk through a Two Sum solution with a map, inspect each lookup, and use a trace to understand why checking before inserting matters.
Two Sum asks for the indices of two numbers that add up to a target. The important detail is that you cannot use the same element twice.
For nums = [2, 7, 11, 15] and target = 9, the answer is [0, 1]: the numbers at those positions are 2 and 7.
Keep track of what you have already seen
At each index, ask: which number would complete the pair? Subtract the current number from the target to find its complement.
A map can associate each earlier number with its index. Check that map for the complement before saving the current number.
function twoSum(nums, target) {
const seen = new Map();
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 [];
}
The map contains only numbers from earlier indices. That makes it possible to find a partner without reusing the current element.
Trace the first example
Follow the map as the loop advances. The map shown below is its state before the lookup.
| Index | Current number | Complement | Map before lookup | Action |
|---|---|---|---|---|
| 0 | 2 | 7 | Empty | Save 2 → 0 |
| 1 | 7 | 2 | 2 → 0 |
Return [0, 1] |
The function returns during the second iteration. It never needs to inspect 11 or 15.
Check before inserting
Suppose the input is [3, 2, 4] and the target is 6. At index 0, the complement of 3 is also 3.
If you insert the current number first, the map already contains 3 → 0 when you look up the complement. An incorrect implementation could return [0, 0] and reuse one element.
Checking first avoids that mistake. The loop eventually matches 2 at index 1 with 4 at index 2, returning [1, 2].
Try repeated values
For [3, 3] with a target of 6, two equal values at different indices form a valid answer.
- At index
0, the map is empty. Save3 → 0. - At index
1, the complement3is already in the map at index0. - Return
[0, 1].
The check is about using different indices, rather than requiring different values.
Take the trace into the editor
Start with the Two Sum question in the editor. Write the solution, then follow the current index, complement, and map as the code runs in the visualizer.
Before each iteration, predict the next lookup and the map’s contents. Compare that prediction with the trace. If they disagree, pause at that step and work out which assumption changed.