The problem with the obvious approach#
You have an array and you want to find two values that add up to a target. The first idea anyone has is to try every pair: for each element, walk the rest of the array looking for its partner.
That works, and for an array of 10 elements it is instant. For 200000 elements it is 20 billion comparisons, which is not instant at all. Two nested loops over the same array is O(n^2) time, and that quadratic is what makes the difference between a solution that is accepted and one that times out.
The question to ask#
When you are inside the inner loop, what are you actually asking? For the current element x, you are asking: have I seen target - x anywhere?
That is a membership question, not a search. Searching an array for a value costs O(n) because you have to look at everything. Asking a hash map whether it holds a key costs O(1) on average, because the key itself tells the map where to look.
So keep a map as you go. For each element, first ask whether its partner is already in the map. If it is, you are done. If it is not, put the current element in the map and move on.
Why one pass is enough#
It is tempting to fill the whole map first and then search it. That works too, but it needs care: [3, 3] with target 6 is fine, while [3, 4] with target 6 would match 3 with itself if you are not careful.
Building the map as you go removes the problem entirely. When you look up target - x, the map contains only elements that came before x, so a match is always a different element. Every pair is still considered, because each pair has a later element, and that later element does the asking.
The cost#
- Time:
O(n). One pass, constant work per element. - Memory:
O(n). In the worst case every element goes into the map.
That trade is the whole idea, and it comes up constantly: you spend memory to remember what you have already seen, so you never have to look at it again.
Where this shows up#
Any time the inner loop of a nested pair of loops is asking have I seen this before, a hash map removes it. Counting duplicates, finding the first repeated character, grouping words by their sorted letters, checking whether a subarray sum has occurred before: all the same move.
Common mistakes#
- Using the map before inserting, or after, without thinking about which. Insert after the lookup.
- Storing the value when you need the position. Store what you will have to report.
- Assuming the input has a unique answer when the statement does not say so.