Solve the Two Sum Problem
Learn the O(n) hash map solution to the Two Sum problem and how to explain it clearly in a coding interview.
Expected Interview Answer
The optimal solution to Two Sum scans the array once while keeping a hash map of value to index, checking on every element whether its complement (target minus current value) has already been seen, which gives O(n) time and O(n) space instead of the brute-force O(n squared).
The brute-force approach checks every pair with nested loops, comparing each element against every other element until a pair sums to the target. The hash map approach avoids the second loop entirely: for each number, compute the complement needed to reach the target, and look it up in a map built from numbers already visited. If the complement exists, you have found the pair in a single pass; if not, insert the current number and its index and continue. Because hash map lookups are O(1) on average, the whole algorithm runs in O(n) time, trading extra memory for speed. This complement-lookup pattern generalizes far beyond Two Sum, showing up in Three Sum, subarray-sum problems, and any task that reduces to "have I seen the value that completes this pair."
- Single pass, O(n) time complexity
- O(n) extra space for the hash map
- Avoids nested-loop brute force
- Pattern reused in many sum-based problems
AI Mentor Explanation
A scorer needs two overs whose combined runs hit an exact target score for a trivia segment. Instead of comparing every over against every other over, the scorer walks through the innings once, and after each over checks a running notebook for an over whose runs would exactly complete the target with the current over. If that complementary over is already in the notebook, the pair is found instantly; otherwise the current over's runs get written into the notebook and the scorer moves on. This notebook lookup replaces a slow pairwise comparison with a single sweep through the innings.
Step-by-Step Explanation
Step 1
Initialize an empty hash map
Map holds each visited value to its index as you iterate.
Step 2
Compute the complement
For the current element, complement = target - nums[i].
Step 3
Check the map for the complement
If present, return the stored index and the current index as the answer.
Step 4
Insert and continue
If not present, store nums[i] to index i in the map and move to the next element.
What Interviewer Expects
- Identify the brute-force O(n squared) approach first, then optimize
- Explain why a hash map reduces lookup to O(1) average
- State final complexity: O(n) time, O(n) space
- Handle the case of duplicate values and no valid pair correctly
Common Mistakes
- Using the same element twice by not excluding the current index
- Building the entire map before scanning instead of checking-then-inserting in one pass
- Forgetting the problem usually assumes exactly one valid answer
- Not discussing the space-time tradeoff versus the brute-force approach
Best Answer (HR Friendly)
“Two Sum asks you to find two numbers in an array that add up to a target. I solve it by walking through the array once and keeping a running note of numbers I have already seen; for each new number I check whether its missing half is already in that note, which lets me find the pair in a single pass instead of comparing every number against every other number.”
Code Example
def two_sum(nums, target):
seen = {} # value -> index
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return [] # no valid pair found
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]Follow-up Questions
- How would you solve Two Sum if the array were already sorted?
- How would you extend this approach to Three Sum?
- What happens if the array contains duplicate numbers?
- How would you return all valid pairs instead of just one?
MCQ Practice
1. What is the time complexity of the hash-map approach to Two Sum?
A single pass with O(1) average hash map lookups gives O(n) overall time complexity.
2. What does the hash map store in the optimal Two Sum solution?
The map records value-to-index for each element seen so far, enabling O(1) complement lookups.
3. Why is the brute-force nested-loop approach to Two Sum inefficient?
Checking every possible pair with nested loops costs O(n squared) time, which the hash map approach avoids.
Flash Cards
What is the optimal time complexity for Two Sum? — O(n), using a single pass with a hash map.
What does the hash map key and value represent in Two Sum? — Key is the number seen; value is its index in the array.
What is the complement in Two Sum? — target minus the current number, the value needed to complete the pair.
What is the space complexity of the hash map approach? — O(n), for storing up to n values in the map.