Two Sum

Problem

Given an array of integers and a target sum, return the indices of the two numbers that add up to the target. Each input has exactly one solution, and you may not use the same element twice.

Input: nums = [2, 7, 11, 15], target = 9   → [0, 1]   (2 + 7 = 9)
Input: nums = [3, 2, 4],       target = 6   → [1, 2]   (2 + 4 = 6)
Input: nums = [3, 3],          target = 6   → [0, 1]

Solution

Approach - hash map complement lookup in a single pass.

The brute force tries every pair, which is O(n²). The insight is that for any element num, the partner you need is fixed: target - num. So instead of scanning the rest of the array to find that partner, you keep a running dictionary of every value you have already passed, mapping it to its index. As you walk left to right, for each num you first ask "have I already seen its complement?" - a single O(1) dict lookup. If yes, the pair is complete and you return both indices. If no, you record seen[num] = index and move on, so the value becomes available as a complement for a later element.

The ordering of the two operations is what makes it correct. You check complement in seen before inserting the current element, so an element can never pair with itself - only with something strictly earlier. Trace [2, 7, 11, 15], target 9: at index 0, complement 7 is not in seen, so store {2: 0}. At index 1, complement 2 is in seen at index 0, so return [0, 1]. The earlier index naturally comes first.

Edge cases - duplicate values like [3, 3] work because index 0 is stored before index 1 looks it up. The check-before-insert guard prevents matching an element with itself when 2 * num == target.

Complexity - O(n) time, O(n) space - one pass with constant-time dict operations, and the dict can hold up to n entries.