Patterns / Two Sum walkthrough

Two Sum — A Worked Walkthrough

From brute force to the optimal one-pass hash-map solution, step by step.

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.

Start with brute force

The most direct idea: try every pair and check whether it sums to the target. It always works, and stating it shows the interviewer your baseline before you optimize.

for (int i = 0; i < nums.length; i++)
    for (int j = i + 1; j < nums.length; j++)
        if (nums[i] + nums[j] == target)
            return new int[]{ i, j };
return new int[]{ -1, -1 };

This is O(n²) time and O(1) space. For large arrays the nested scan is too slow, so the question becomes: can we avoid re-checking every pair?

The key insight

For each number x, its partner is fixed: it must be target - x. So instead of searching the rest of the array for that partner, we can remember the numbers we have already seen in a hash map and ask, in O(1), "have I seen target - x before?"

The optimal solution

Map<Integer, Integer> seen = new HashMap<>(); // value -> index
for (int i = 0; i < nums.length; i++) {
    int need = target - nums[i];
    if (seen.containsKey(need)) {
        return new int[]{ seen.get(need), i };
    }
    seen.put(nums[i], i);
}
return new int[]{ -1, -1 };

One pass, O(n) time and O(n) space. We check for the partner before inserting the current value, which guarantees we never pair an element with itself.

A quick dry run

Take nums = [2, 7, 11, 15], target = 9:

1. i=0, x=2, need=7. Map is empty → store {2:0}.
2. i=1, x=7, need=2. Map has 2 at index 0 → return [0, 1]. Done.

Edge cases to mention

• Duplicate values, e.g. [3, 3] with target 6 — storing index as you go handles this correctly.
• Negative numbers and zero — the arithmetic is unchanged.
• No valid pair — decide on a sentinel return or exception (the prompt here guarantees one).

The takeaway

Two Sum is the canonical hashing & counting problem: whenever a brute-force solution rescans the data looking for a complementary value, a hash map usually collapses the inner loop into an O(1) lookup. Try it yourself, then look for the same shape in Two Sum II, 3Sum, and Subarray Sum Equals K.