Two-Sum and Its Many Variants
Solve two-sum, three-sum, four-sum, and two-sum with sorted array using hash maps and two pointers, comparing time and space costs.
Two-Sum: The Classic Interview Problem
LeetCode 1 'Two Sum': given an unsorted array and a target, return the indices of two elements that add up to the target. The brute-force O(n²) approach checks all pairs. The optimal O(n) approach uses a hash map: for each element x, check if target - x already exists in the map. If yes, return the pair of indices. If no, store x and its index in the map.
Two-sum is often the very first problem in an interview — knowing it cold signals that you are ready to move to harder problems.
def twoSum(nums, target):
seen = {} # val -> index
for i, x in enumerate(nums):
complement = target - x
if complement in seen:
return [seen[complement], i]
seen[x] = i
return []
print(twoSum([2, 7, 11, 15], 9)) # [0, 1]
print(twoSum([3, 2, 4], 6)) # [1, 2]
print(twoSum([3, 3], 6)) # [0, 1]Why the Hash Map Works for Two-Sum
The hash map stores every element seen so far. When processing element x, if target - x is in the map, those two elements form a valid pair. Crucially, the complement is always checked before x is stored, preventing the case where a single element is paired with itself (e.g., if x == target/2, the map check happens before x is stored, so it won't match unless there are two copies).
# Trace two-sum on [2, 7, 11, 15], target=9
nums, target = [2, 7, 11, 15], 9
seen = {}
for i, x in enumerate(nums):
complement = target - x
print(f'i={i} x={x} complement={complement} seen={seen}')
if complement in seen:
print(f' Found: indices [{seen[complement]}, {i}]')
break
seen[x] = i