Hash Map: Two Sum on an Unsorted Array, From O(n²) to One Pass
One problem, three stages: make it work, make it fast, make it lean. Step through each stage in the visualizer, then run all three on a big input in the benchmark and watch the brute force overheat.
The real-world version
An expense system flags pairs of transactions that together hit an approval limit exactly, a classic way to split a purchase and dodge sign-off. Transactions arrive in no particular order, and the answer must point back to the original rows.
The problem
Given an unsorted array nums and an integer target, return the indices of the two numbers that add up to target. Each input has at most one answer.
nums = [7, 2, 9, 4, 11, 5], target = 15 → (3, 4) # 4 + 11
Stage 1 · Smelt: Make it work
Try every pair of positions. Simple, obviously correct, and the baseline every faster version has to beat.
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 NoneWhy it's not enough: Quadratic: doubling the input makes it four times slower.
Stage 2 · Hammer: Make it fast
Sorting would let us use two pointers, but sorting loses the original positions. So sort (value, index) pairs, then walk in from both ends.
def two_sum(nums, target):
pairs = sorted((x, i) for i, x in enumerate(nums))
l, r = 0, len(pairs) - 1
while l < r:
s = pairs[l][0] + pairs[r][0]
if s == target:
return tuple(sorted((pairs[l][1], pairs[r][1])))
if s < target:
l += 1
else:
r -= 1
return NoneWhy it's not enough: Much faster, but the sort dominates and we copy the input just to remember indices.
Stage 3 · Polish: Make it lean
Walk once. For each number, ask the map: "have I already seen target - x?" If yes, you're done; if not, store x → index. Checking before storing also handles [3, 3] with target 6 correctly.
def two_sum(nums, target):
index_of = {} # value -> index
for i, x in enumerate(nums):
j = index_of.get(target - x)
if j is not None:
return j, i
index_of[x] = i # store AFTER checking
return NoneWhy it holds up: Optimal for unsorted input: every element is looked at once and lookups are O(1) on average.
X-ray: watch it run
Benchmark: will the forge overheat?
Run all three stages on a large input in your browser and compare the work each one does.
In the interview
Mention the trade-off: the hash map buys O(n) time with O(n) memory. If the interviewer then says "the input is sorted", switch to two pointers for O(1) space.
Go deeper: Two Sum with Hashing · Hash Table / Hash Map