Two Sum — One-Pass Hash Map
Eliminate the quadratic brute force by caching complements as you sweep the array once.
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 that each input has exactly one solution and you cannot use the same element twice.
Why This Problem Matters
- Introduces the "store what you need later" pattern which reappears in subarray sum, two-number sum, and complement-based problems.
- Builds intuition for favouring linear-time scans coupled with constant-time lookups over nested loops.
- Serves as a gentle entry point for thinking in terms of invariants: every index either solves the problem immediately or contributes information for future iterations.
Thought Process
Start with the baseline
A double loop that tests every pair works but costs O(n^2). Recognise that repeated work happens because we recompute sums we have already considered.
Ask what information unlocks the answer sooner
For each number, you want another value that equals target - current. If that complement has already appeared, you are done. You only need constant-time access to that complement.
Choose a structure that answers membership fast
A hash map lets you store the complement you still need along with its index in O(1) average time. The moment the current value satisfies a stored complement, you have the answer.
Validate invariants
Before processing index i, the map stores the complement for every prior value alongside that value’s index. If the solution uses (i, j) with j < i, its complement was inserted when you processed j, so you return as soon as you reach i.
Step-by-Step Reasoning
- Initialise an empty Map needed from complement → index.
- Iterate nums with index i and value num.
- If needed contains num, return [needed.get(num), i] immediately.
- Otherwise compute complement = target - num and store needed.set(complement, i).
Dry Run
i = 0, num = 2, complement = 7
No match yet; store needed[7] = 0 so a future 7 resolves the pair.
i = 1, num = 7, complement = 2
needed already has 7 → 0, so return [0, 1].
Complexity Analysis
Time
O(n)
Space
O(n)
Why
Each element is processed once and stored at most once; Map lookups and inserts are O(1) on average.
Annotated Solution
import java.util.HashMap;
import java.util.Map;
public class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> needed = new HashMap<>();
for (int i = 0; i < nums.length; i += 1) {
int value = nums[i];
if (needed.containsKey(value)) {
return new int[]{needed.get(value), i};
}
needed.put(target - value, i);
}
return new int[]{-1, -1};
}
}Instead of caching numbers we already saw, we cache the complement each number requires. When the current value matches a stored complement we immediately return the recorded complement index and the current index.
Common Pitfalls
- Forgetting that the same value can appear twice (e.g., nums = [3, 3], target = 6). Storing latest index still works because the first occurrence is in the map before you process the second.
Follow-Up Questions
- How would you adapt the solution if you needed all unique pairs instead of a single pair? (Store indices in arrays and continue scanning.)
- What if the array is sorted? (Use the two-pointer pattern instead of a hash map to save space.)