Two Sum
Problem Statement
Given an integer array nums and an integer target, return the indices of the two numbers such that they add up to target. You may assume exactly one valid answer exists, and you may not use the same array element twice.
Input
An integer array nums and an integer target.
Output
An integer array containing the two indices whose values sum to target. Any valid order is acceptable.
Constraints
- •
2 <= nums.length <= 10^4 - •
-10^9 <= nums[i] <= 10^9 - •
-10^9 <= target <= 10^9 - •
Exactly one valid answer exists
Examples
Example 1
nums = [2, 7, 11, 15], target = 9
[0, 1]Example 2
nums = [3, 2, 4], target = 6
[1, 2]Example 3
nums = [3, 3], target = 6
[0, 1]Learning Objectives
- Recognise a pair-sum question as a complement lookup problem.
- Replace the nested-loop search with a one-pass hash map from value to index.
- Explain why checking before inserting prevents using the same index twice.
- Handle duplicate values without losing the valid earlier index.
Intuition
Pattern Recognition
The signal is a question about two values that must combine to a target. The direct approach tries every pair, which costs O(n^2). A hash map lets you ask the better question at each index: if the current value is x, have I already seen target - x?
This is not a frequency counting problem yet; it is a complement lookup problem. Store only values from the left side of the scan. Then every match uses one earlier index and the current index, so the same element is never reused.
Common mistakes
- ×Inserting the current value before checking its complement, which can accidentally pair an element with itself when **target = 2 * nums[i]**.
- ×Using a set instead of a map and then having no way to return the earlier index.
- ×Overwriting duplicate values in a way that hides the index needed by the current complement.
- ×Continuing the scan after the answer is found even though the problem guarantees exactly one answer.
Algorithm Explanation
Key idea
Keep a hash map from each value already seen to its index. At index i, compute target - nums[i]. If that complement is in the map, the earlier index and i are the answer. Otherwise, store the current value for future elements.
Walkthrough
For nums = [2, 7, 11, 15] and target = 9, start with an empty map. At index 0, value 2 needs complement 7, which is not present, so store 2 -> 0. At index 1, value 7 needs complement 2, which is already in the map at index 0. Return [0, 1] immediately.
Algorithm
- Create an empty hash map indexByValue.
- Scan nums from left to right.
- For the current value, compute complement = target - value.
- If complement exists in the map, return its stored index and the current index.
- Otherwise store the current value with the current index.
- The loop should always return because the input guarantees one valid answer.
Solutions
Solution: One-pass complement map
Store only numbers that appear before the current index. That turns each candidate pair into one expected O(1) lookup while preserving the exact index needed for the answer.
Step-by-step
- Initialise an empty HashMap<Integer, Integer> from value to index.
- For each index, compute the complement needed to reach target.
- If the complement is already in the map, return the previous index and the current index.
- If not, insert the current value and index for later numbers.
- Return an empty array only as a defensive fallback for invalid inputs.
O(n)
O(n)
Each value is inserted and looked up at most once; the map can hold up to n values.
Java implementation
Dry Run
Sample input
nums = [2, 7, 11, 15], target = 9. Track the complement lookup before each insertion.
| step | index | value | complement | map before lookup | action |
|---|---|---|---|---|---|
| 1 | 0 | 2 | 7 | empty | 7 missing, store 2 -> 0 |
| 2 | 1 | 7 | 2 | 2 -> 0 | 2 found at index 0, return [0, 1] |
The answer appears as soon as the current value can pair with a value seen on its left.
Interview Tips
Lead with the complement question: for each value, what earlier value would finish the pair? Then explain the order of operations: check first, insert second. That small detail proves you never reuse the same element and handles duplicates like [3, 3] cleanly.
Likely follow-ups
- What changes if the input is sorted and you only need the values, not original indices?
- How would you return all unique pairs that sum to **target**?
- How would the approach change for Three Sum?
- What if numbers arrive as a stream and queries ask whether any pair sums to a target?
Similar Problems
Key Takeaways
- Two Sum is a complement lookup problem, not a nested-loop problem.
- The map stores values from the left side of the scan so indices stay distinct.
- Checking before inserting avoids pairing an element with itself.
- Hash maps often buy linear time by spending linear space.