How do you solve the Two Sum problem efficiently?
In Two Sum you must find two numbers in an array that add up to a target. The brute force way checks every pair in O(n squared). The efficient way uses a hash map to remember numbers you have seen, so for each number you check if the target minus that number is already stored. This runs in O(n) time and O(n) space.
- Two Sum asks for two numbers in an array that add up to a target.
- Brute force checks every pair in O(n squared), which is correct but slow.
- A hash map remembers seen numbers so you find the pair in O(n) time and O(n) space.
The brute force idea
Check every pair of numbers and see if they add to the target. It works but is slow because it does about n times n comparisons.
The efficient hash map idea
As you walk the array once, ask whether the number that would complete the pair has already been seen. Store each number in a hash map so this check is instant.
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> seen;
for (int i = 0; i < nums.size(); i++) {
int need = target - nums[i];
if (seen.count(need))
return {seen[need], i};
seen[nums[i]] = i;
}
return {};
}int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (seen.containsKey(need))
return new int[]{seen.get(need), i};
seen.put(nums[i], i);
}
return new int[]{};
}def two_sum(nums, target):
seen = {}
for i, n in enumerate(nums):
need = target - n
if need in seen:
return [seen[need], i]
seen[n] = i
return []Interviewers love to see you start with brute force, state its complexity, then improve it with a hash map. Narrating that jump from O(n squared) to O(n) is exactly the thought process they are testing.
Frequently asked questions
What is the time and space complexity of the hash map solution?
It is O(n) time because you pass through the array once, and O(n) space because the hash map can hold up to n numbers.
What if the array is already sorted?
You can use the two pointer technique instead, moving one pointer from each end. That solves it in O(n) time and O(1) extra space.
Common follow up questions
Related interview questions
Want the full DSA guide?
Read every DSA concept with notes, diagrams, and code in one place. Track your progress as you go.
Open the DSA guide All DSA questions