Hash Map Complement Lookup

Foundations

In the first lesson, a set answered whether a value had appeared. Now, what if you also need to know where it appeared, or which earlier value pairs with the current one?

A hash map, a dictionary in Python, stores keys like a set but attaches a value to each key. seen[x] = i files index i under key x, and seen[x] reads it back in O(1). The key picks the bucket exactly as in a set; the value rides along. Asking x in seen for a key never stored answers False without a scan.

Complement lookup uses that to find pairs. On nums = [7, 1, 5, 3, 6], suppose you want two values that add up to 11. At each index, compute the partner the current value needs, 11 - x, and look it up before storing x with its index. At index 4, x is 6 and needs 5, which the map stored at index 2, so one lookup returns [2, 4].

Case Scenario

Two Sum is that lookup with the sum given as target. In nums = [3, 2, 4] with target = 6, the answer is [1, 2], because 2 + 4 = 6. The two indexes must differ, so index 0's 3 cannot pair with itself, even though 3 + 3 is also 6.

The direct approach tries every pair of indexes i < j and checks nums[i] + nums[j] == target. It needs no extra memory, but checks up to n(n - 1)/2 pairs, so the work grows with the square of the input. As in the first lesson, each new i rereads every later value; the fix is to let each value ask for its partner once.