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.
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.
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.
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