Two Sum
Understanding the Problem
We need to find two distinct positions in the array whose values sum to the target. The problem guarantees exactly one solution exists, so we don't need to worry about multiple matches or no matches.
The detail that shapes our approach: we need to return indices, not the values themselves. Any approach that loses track of original positions, like sorting the raw array without remembering where each element came from, needs extra bookkeeping. So the core question for each element nums[i] is whether target - nums[i] exists somewhere else in the array, and if so, at which index.
Key Constraints:
2 <= nums.length <= 10^4→ With n up to 10,000, an O(n^2) brute force does about 50 million comparisons in the worst case, which passes within typical time limits but is slow. An O(n) solution is the goal.-10^9 <= nums[i] <= 10^9→ Values can be negative, so the complementtarget - nums[i]can also be negative. Bothtarget - nums[i]and the pair sum stay within [-2x10^9, 2x10^9], which fits in a signed 32-bit integer (max about 2.147x10^9), so there is no overflow.Only one valid answer exists→ We can return as soon as we find the pair. There is no need to handle duplicate answers or keep searching after a match.
Approach 1: Brute Force
Intuition
Check every possible pair. For each element, look at every later element to see if the two add up to the target. This is the same method you would use by hand on a short list of numbers. It works for any input size but slows down on large arrays.
Algorithm
- Use two nested loops: the outer loop picks the first element at index
i, the inner loop picks the second element at indexj(wherej > i). - For each pair
(i, j), check ifnums[i] + nums[j] == target. - If the condition holds, return
[i, j]. - Since the problem guarantees exactly one solution, we'll always find a match before exhausting all pairs.
Example Walkthrough
Code
- Time Complexity: O(n^2). The outer loop runs n times, and the inner loop runs up to n-1 times per iteration. In the worst case, we examine n*(n-1)/2 pairs.
- Space Complexity: O(1). We only use a couple of loop variables. No extra data structures.
The cost comes from the inner scan: for each element we look through the rest of the array to find its complement, which is O(n) per element. The next approach replaces that scan with a constant-time lookup.
Approach 2: Hash Map (One Pass)
Intuition
For each element nums[i], the value that completes the pair is fixed: target - nums[i]. The brute force finds this complement by scanning the array, which costs O(n) each time. A hash map turns that scan into an O(1) lookup.
As we iterate, we store each value and its index in a hash map. Before storing the current element, we check whether its complement is already in the map. If it is, we have the pair. If not, we add the current element and continue.
This needs only a single pass. By the time we reach the second element of the answer pair, the first element is already in the map, so a single lookup finds it.
The order of operations matters: we check for the complement before inserting the current element. Because the current index is not yet in the map when we look it up, an element can never match itself, even when target is twice its value. The map only ever holds elements at strictly earlier indices, so any match it returns is a genuine pair of distinct positions.
Algorithm
- Create an empty hash map that maps values to their indices.
- Iterate through the array with index
i. - Compute the complement:
complement = target - nums[i]. - Check if
complementexists in the map. If yes, return[map[complement], i]. - If not, add
nums[i] -> ito the map. - Continue until the pair is found.
Example Walkthrough
Code
- Time Complexity: O(n). We iterate through the array once. Each hash map lookup and insertion is O(1) on average, so the total work is O(n).
- Space Complexity: O(n). In the worst case, we store n-1 elements in the map before finding the answer.