You open the shared editor, the interviewer pastes a prompt, and it’s Two Sum: an array of integers, a target value, return the indices of the two numbers that add up to it. It reads like a throwaway, and that’s the point. This is still the warmup at Google, Meta, and Amazon, and at most of the startups that copied those loops, because it separates the people who reach for the first thing that works from the people who reach for the right thing and can say why.
What the interviewer wants to watch in the next ten minutes is a small arc. You state the brute-force idea, you name its cost, you find the better approach, and you justify the trade you made to get there. Land that arc on an easy problem and you’ve shown the exact skill they’re screening for on the hard ones.
Start with the version that obviously works
Check every pair. For each element, look at every element after it and test whether the two add up to the target.
def two_sum(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
Say it’s correct before you say anything against it. It runs in O(n^2) time, because the inner loop reruns for every position of the outer one, and it uses O(1) extra space. On ten elements nobody cares. On 100,000 elements that’s roughly five billion comparisons, and the interviewer is now waiting to hear you notice.
The one-pass hash map
The waste in the brute force is that you keep re-scanning the array to answer one small question: for the number in front of me, has its partner already gone by? A hash map answers that in constant time. Walk the array once. For each value x, the number you need is target minus x. If you have already stored that number, you are done. If not, record x with its index and move on.
def two_sum(nums, target):
seen = {}
for i, x in enumerate(nums):
need = target - x
if need in seen:
return [seen[need], i]
seen[x] = i
return []
One pass, O(n) time, O(n) space. The detail that trips people up is the ordering: you check for the complement before you insert the current number. Flip those two lines and a target of 6 with a single 3 in the array would match that 3 against itself and hand back a wrong answer. Checking first means seen only ever holds elements to the left of where you are, so the index you return belongs to a genuinely different element.
Why a single pass is enough
The move here shows up in a hundred other problems: spend memory to skip repeated work. Brute force asks ‘is there a partner for x?’ by looking forward through the whole array every single time. The hash map flips the direction. By the time you reach x, every earlier number is already on record, so ‘did x’s partner come before it?’ collapses to one lookup. You never look forward, only back, and looking back is free because you have been writing things down the whole way.
That is also why the cost is O(n) and nothing subtler. Each element gets one insert and one lookup, both averaging constant time, so the work scales with the length of the array. Space is O(n) in the worst case, where you scan nearly the whole array before the pair turns up and the map ends up holding almost every element. If an interviewer pushes you to cut that space, the right reflex is to ask whether the array is sorted, which changes the problem entirely.
The seen-the-complement pattern
Two Sum lasts because the technique outlives the question. The shape is simple: as you scan, compute what you would need to have already seen, then check a hash map for it. Subarray Sum Equals K runs it on prefix sums. Finding the first character that repeats runs it on counts. Longest Consecutive Sequence uses a set, the same idea with the index thrown away. Once ‘write down what I’ve seen, query for the complement’ is automatic, a big chunk of the medium array and string problems stop reading like separate puzzles.
That is why a good interviewer is glad to see you write the hash-map version fast and then name the pattern. Speed by itself reads as memorization. Speed plus ‘this is the seen-the-complement trick, the same one behind the subarray-sum problems’ reads as someone who will carry the idea into a problem they have not drilled.
The edge cases they poke at
The follow-ups are predictable, and having the answers loaded is most of the polish.
- Can a number pair with itself? No, and the check-before-insert ordering handles it for free, which is worth saying out loud rather than hoping they spot it.
- Duplicates, like [3, 3] with target 6? Fine: the first 3 goes into the map, the second 3 finds it. Returning indices instead of values is what keeps this clean.
- No pair exists? Return an empty result, or whatever the prompt asks for, but make the decision instead of letting the function run off the end.
- More than one valid pair? The classic version promises exactly one answer. If the interviewer drops that promise, ask whether they want the first pair, every pair, or just a count, because each one changes the code.
When the array is sorted, drop the map
Two Sum II hands you a sorted array and asks the same question. Now you can do it in O(1) extra space with two pointers, one at each end. Add the ends. Too small, move the left pointer right for a bigger sum. Too big, move the right pointer left. Equal, you’re done.
def two_sum_sorted(nums, target):
lo, hi = 0, len(nums) - 1
while lo < hi:
total = nums[lo] + nums[hi]
if total == target:
return [lo, hi]
if total < target:
lo += 1
else:
hi -= 1
return []
It works because sorting gives the sum a direction. From any pair, moving a pointer inward changes the total in a known way, so you never backtrack. The catch is that it needs sorted input. If the array is unsorted and you sort it yourself, you pay O(n log n) and you scramble the original positions, which matters when the question wants indices into the original array. That trade is the whole decision.
| Approach | Time | Extra space | Reach for it when |
|---|---|---|---|
| Brute force | O(n^2) | O(1) | Almost never, but say it first to anchor the improvement |
| Hash map, one pass | O(n) | O(n) | Unsorted array and you need original indices |
| Two pointers | O(n) | O(1) | Array is already sorted, or you only need the values |
Where it leads: 3Sum and subarray sums
3Sum is Two Sum wearing a coat. Sort the array, fix one element, and run the two-pointer search across the rest for the value that completes the triple. 4Sum nests that one layer deeper. The two-pointers-on-a-sorted-array half of those solutions is exactly the routine above, which is why interviewers treat fluency on the easy version as a prerequisite rather than a bonus.
If you want to practice the reflex instead of memorizing the answer, try this order: solve Two Sum, re-solve it for a sorted input, then write Subarray Sum Equals K from scratch and watch yourself reach for the same hash map before anyone tells you to. The two numbers were never the test. What they are watching is whether you can notice, mid-problem, that the thing you need to look up is something you already walked past.
Drill the patterns next:
