Two Sum

Two Sum is the first problem almost everyone solves, and the hash map is the answer almost everyone memorises. What makes this family worth reading top to bottom is that the hash map is optimal for exactly one member of it. Every question after the first either hands you a property that makes the map unnecessary, or asks for something the map cannot express - and an interviewer walking you up this ladder is checking whether you noticed, or whether you are reaching for the same tool because it is the only one you packed.

The through-line: what does the input let you assume, and what is the answer actually shaped like?

1: the map earns its keep

note

What the input gives you: nothing. The array is unsorted, so there is no structure to exploit and no way to know where a complement might live. Trading O(N) memory for the lookup is the honest deal, and the page's three solutions are really three points on that trade: pay O(N^2) time and no memory, pay two passes, or pay one.

1. Two Sum

Easy·

1Two Sum

3 Approaches

All Pairs

O(n^2) timeO(1) aux

Prefilled Index Map

O(2n) timeO(n) aux

Lookup Before Insert

O(n) timeO(n) aux

FIG. 1 TWO SUM ALL PAIRS● INTERACTIVE

visualization loads as you reach it

class Solution:

def twoSum(self, nums: List[int], target: int) -> List[int]:

n = len(nums)

for i in range(n):

for j in range(n):

if i != j and nums[i] + nums[j] == target:

return [i, j]

---

167: sorted input is already a map

note

What changed: the array arrives sorted, and the problem asks for O(1) extra space. Those two clauses are the same clause. Sorted order means a pair that sums too high can only be fixed by pulling the right pointer in, and a pair that sums too low only by pushing the left pointer out, so the converging two-pointer walk finds the answer in one pass with nothing stored. The hash-map solution still works and is still on this page as "Lookup Before Insert" - it just now costs O(N) memory to rediscover an ordering you were handed for free. Bringing it up here is the tell an interviewer is listening for.

167. Two Sum II - Input Array Is Sorted

Medium·

167Two Sum II - Input Array Is Sorted

3 Approaches · 3 patterns

Converging Pointers↗ Two Pointers

O(N) timeO(1) aux

Lookup Before Insert↗ Hash & Set

O(N) timeO(N) aux

Complement by Bisect↗ Binary Search

O(N log N) timeO(1) aux

Borrowed from Array & String / Two Pointers / Left / Right Heads - shown here in full

FIG. 167 TWO SUM II INPUT ARRAY IS SORTED● INTERACTIVE

visualization loads as you reach it

class Solution:

def twoSum(self, numbers: List[int], target: int) -> List[int]:

left, right = 0, len(numbers) - 1

while left < right:

total = numbers[left] + numbers[right]

if total < target:

left += 1

elif total > target:

right -= 1

else:

return [left + 1, right + 1]

return [-1, -1]

---

15 and 18: the answer stops being a single pair

3Sum and 4Sum are not in this repo yet, so there is nothing to embed - but they are where the family turns.

Both ask for every distinct tuple rather than one, and that single change invalidates the habit both earlier problems taught. You can no longer return on first match, so the "find it and get out" shape is gone. Worse, a hash map over values now actively fights you: the hard part is no longer finding a complement but avoiding reporting the same triple three times, and a map keyed by value has thrown away exactly the positional information you need to dedupe cheaply.

The move is to stop resisting the sort. Sort the array, fix the outer index (or two), and run 167's converging-pointer scan on the remainder - skipping over equal neighbours to dedupe as you go. 3Sum is 167 wrapped in one loop, 4Sum is 167 wrapped in two. That is the whole insight, and it is why 167 is worth understanding properly rather than filing away as "the easy sorted one".

454 (branch): the map comes back, keyed differently

4Sum II is the member people misfile as "just harder 4Sum". It is not on the same ladder at all.

It hands you four separate arrays and asks how many index tuples sum to zero - a count, not the tuples themselves. Nothing needs deduplicating, because tuples from four distinct arrays are distinct by construction, and nothing needs to be reported, so there is nothing for the two-pointer scan to build. Split the four arrays into two halves, hash every pairwise sum of the first half, then look up the negation of every pairwise sum of the second: O(N^2) time and O(N^2) space.

So the map returns the moment the answer collapses back to a scalar. The lesson of this chain is not "hash maps are for unsorted input" - it is that the technique follows the answer's shape at least as much as the input's.

The constraint matrix

Problem	Title	Input	Answer shape	Best time	Aux space
1the hub	Two Sum	Unsorted	One pair of indices	O(N)	O(N)the index map
167from 1	Two Sum II	Sorted	One pair of indices	O(N)	O(1)the sorting is the map
15from 167	3Sum	Unsorted	All unique triples	O(N^2)	O(1)beyond the sort
18from 15	4Sum	Unsorted	All unique quadruples	O(N^3)	O(1)beyond the sort
454from 18	4Sum II	Four separate arrays	A count, not the tuples	O(N^2)	O(N^2)the map comes back

Read the last two columns together. The moment the answer stops being "one pair" and becomes "every distinct tuple", returning early stops being allowed and deduplication becomes the real work. And the moment the answer collapses back to a single number, the map becomes the right tool again - which is why 454 is the odd one out rather than simply the hardest.