DSAWiser

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.

ArraysHash mapsCode visualization
On this page

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.

  1. At index 0, the map is empty. Save 3 → 0.
  2. At index 1, the complement 3 is already in the map at index 0.
  3. 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.

Practice this topic

Explore practice sets Open DSAWiser editor