Arrays and Hashing
The complement map
Instead of searching for a partner, store what would complete each element and let the partner find you.
The situation
A whole family of problems asks you to find two elements that stand in some fixed relationship to each other. Pairs that differ by k. Pairs that sum to a target. Pairs where one is double the other.
The brute force is always the same: check every pair, O(n squared). The improvement is always the same too, and it is worth learning as one idea rather than as several tricks.
Why it works
The flip
Stop searching for the pair. At each element, work out what its partner would have to be, and ask whether you have already walked past it.
For pairs differing by k, the partner of value is value - k. If it exists earlier in the array, you have already seen it, so you do not need to search. You just need to have remembered.
Here it is for the difference version. Note the order: look up first, record afterwards.
Gotcha
Why recording first breaks it
If you add value to seen before checking, an element can pair with itself. With k = 0 every single element would report a match, because it finds the copy it just inserted.
Checking before recording gives you an invariant worth saying out loud: everything in seen came from a strictly earlier position, so any partner you find is a genuinely different element.
When you need to say where
A set answers whether. If the problem wants the positions of the two elements, swap the set for a dict from value to the index where it appeared. The loop does not otherwise change.
Edge cases
Duplicates are fine
Storing a value that is already in the dict overwrites the earlier index. That sounds like a bug and usually is not, because the return happens the moment a partner is found, before any overwrite could matter.
It does matter when the problem wants every qualifying pair rather than one. Then store a list of indices per value instead of a single index.
Tip
The same idea, rearranged
Whenever the condition relating two elements can be rearranged to isolate one of them, this works. Difference of k gives partner = value - k. A sum target gives a different rearrangement of the same shape. Subarrays summing to k give partner = running total - k, with prefix sums in place of values, which is a genuinely common interview problem hiding under this exact pattern.
Working out the rearrangement for a given problem is the part you have to do yourself. That is the whole skill, and it is the step the problem below is asking for.
Trace the partner lookup
Run index_of_partner on nums = [4, 1, 6, 9] with k = 5, so each element looks for a partner equal to value - 5. Fill in the partner being looked for, whether it was found in seen, and what seen holds after the step. Write the dict as {} when empty, otherwise like {4: 0}. Write found as yes or no.
This activity type is not wired up yet.
Cost of the partner lookup
Give the time and space complexity of the one-pass version above, in terms of n, the length of nums.
Time
Space
Two Sum
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.