Two Sum
Maintained by Vikas D, software engineer
You are given an array of integers nums and an integer target. Return the indices of the two numbers that add up to target.
You can assume each input has exactly one solution, and you may not use the same element twice. Return the two indices in ascending order.
This is the canonical warm-up for the hash-map pattern, and how you solve it says a lot. The naive answer is a double loop; the answer interviewers want trades a little memory for a single pass.
Examples
nums[0] + nums[1] = 2 + 7 = 9, so the answer is the pair of indices 0 and 1.
nums[1] + nums[2] = 2 + 4 = 6. The leading 3 is a distractor; doubling it would need a second 3, which is not present.
Two equal values at different indices are a valid pair. This is the case that breaks a careless solution which lets one element match itself.
Constraints
- 2 <= nums.length
- Exactly one valid pair exists
- Each element may be used at most once
- Return the indices in ascending order
Visible test cases
- twoSum([2,7,11,15], 9) == [0,1]
- twoSum([3,2,4], 6) == [1,2]
- twoSum([3,3], 6) == [0,1]
Hints
Hint 1
A double loop that checks every pair works but is O(n^2). What would let you find the partner of a number without scanning the rest of the array each time?
Hint 2
As you walk the array you always know what you still need: target minus the current value. Could you remember the numbers you have already passed?
Hint 3
Keep a hash map from value to index. Before storing the current number, check whether its complement is already in the map. Checking before inserting is what stops a number from pairing with itself.
Approaches
Brute force
Time O(n^2) · Space O(1)Try every pair of indices and check whether they sum to the target. Correct and easy to reason about, but quadratic, which is too slow once the array is large. Use it only to state a baseline out loud before improving it.
- For each index i from 0 to n-1
- For each index j from i+1 to n-1
- If nums[i] + nums[j] equals target, return [i, j]
One-pass hash map
Time O(n) · Space O(n)Trade memory for time. Walk the array once, keeping a map from each value to the index where you saw it. For the current number compute its complement, target minus the number; if the complement is already in the map you have found the pair. Otherwise record the current number and move on. Because you check before you insert, a value can never pair with itself.
- Create an empty map from value to index
- For each index i, let need = target - nums[i]
- If need is already a key in the map, return [map[need], i]
- Otherwise store map[nums[i]] = i and continue
Common mistakes
- Inserting the current number into the map before checking for its complement, which lets a single element match itself when the target is exactly double that value.
- Returning the values that add up to the target instead of their indices.
- Assuming the array is sorted. The hash-map solution does not need a sorted array, and sorting it first would scramble the original indices you must return.
Follow-up variations
- If the array is already sorted, a two-pointer scan from both ends solves it in O(1) extra space instead of a hash map.
- If more than one valid pair can exist and you must return all of them, the map should store a list of indices per value rather than a single index.
- Three Sum is the natural escalation: fix one index, then run a two-pointer or hash-map pass over the rest to find the remaining pair.