Two Sum: Finding the Pair
The Prompt
Given an array of integers `nums` and an integer `target`, return indices of the two numbers such that they add up to `target`. You may assume that each input would have exactly one solution, and you may not use the same element twice.
Understanding the Problem
You need two indices whose values sum to the target. The brute force checks every pair ā O(nĀ²). The reframe that unlocks O(n): as you scan, for each number ask "have I already seen its complement (target ā current)?"
That question is a membership check ā and constant-time membership is exactly what a hash map sells.
The Interview Flow
Interviewer
Let's start with a classic. Given an array of integers and a target, find the indices of two numbers that sum up to that target.
Candidate
Okay, so for example, if the array is `[2, 7, 11, 15]` and the target is `9`, the output should be `[0, 1]` because `nums[0] + nums[1] == 9`.
Interviewer
Exactly. How would you approach this?
Candidate
A brute-force approach would be to use nested loops. This would be O(n^2) time complexity.
Interviewer
That would work for a small input. Can you think of a more optimal solution?
Candidate
Yes, I can use a hash map to optimize it. I can iterate through the array once. For each element, I'll calculate the complement needed to reach the target (target - current number). Then I check if this complement exists in my hash map.
Interviewer
And what would you store in the hash map?
Candidate
I'd store the number as the key and its index as the value. If the complement is found, I can return the current index and the index from the map. If not, I add the current number and its index to the map. This brings the time complexity down to O(n).
Interviewer
Excellent. That sounds like a solid plan. Please go ahead and code it up.
Why does one pass with a hash map work?
Every valid answer has a later element and an earlier element. When the scan reaches the later one, the earlier one is already in the map ā so checking "complement seen?" at each index is guaranteed to catch the pair exactly once.
You trade O(n) memory for O(n) time. Saying that trade out loud is the interview point, not the code.
Optimal Solution using a Hash Map
- Initialize an empty hash map.
- Iterate through the input array `nums` with both index and value.
- For each number, calculate its complement: `complement = target - current_number`.
- Check if the `complement` exists as a key in the hash map. If it does, we have found our pair. Return the index of the complement from the map and the current index.
- If the complement is not in the map, add the `current_number` and its `index` to the map for future lookups.
- This ensures we only need one pass through the array, achieving O(n) time complexity.
Try it yourself
Write your solution and run it against 3 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function twoSum(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.has(complement)) {
return [map.get(complement), i];
}
map.set(nums[i], i);
}
}Explanation
Scan nums = [2, 7, 11, 15] with target = 9.
1i = 0: complement is 9 ā 2 = 7. The map is empty, so store {2: 0} and move on.
2i = 1: complement is 9 ā 7 = 2 ā already in the map at index 0. Answer: [0, 1]. Done in two steps.
Complexity Analysis
TIME
O(n)
SPACE
O(n)
Finished working through this one?
Mark it complete to track it on your Data Structures path.