Two Sum
Last Updated: March 29, 2026
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 critical detail that shapes our approach: we need to return indices, not the values themselves. This means any approach that loses track of original positions (like sorting the raw array without remembering where each element came from) will need extra bookkeeping. The simplest way to think about it is this: for each element nums[i], we need to find whether target - nums[i] exists somewhere else in the array, and if so, where.
Key Constraints:
2 <= nums.length <= 10^4→ With n up to 10,000, an O(n^2) brute force runs 100 million operations in the worst case. That's borderline but should pass within typical time limits. O(n) is clearly preferred.-10^9 <= nums[i] <= 10^9→ Values can be negative. The complementtarget - nums[i]can also be negative. Don't assume positive numbers only.Only one valid answer exists→ We can return as soon as we find the pair. No need to handle duplicates in the answer or check for multiple solutions.
Approach 1: Brute Force
Intuition
The most natural first thought: just check every possible pair. For each element, look at every other element to see if they add up to the target. This is what you'd do by hand if someone gave you a short list of numbers and asked you to find a pair.
It's not clever, but it works. And for small inputs, it's perfectly fine.
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.
This works but is slow for large inputs. For each element, we scan the rest of the array looking for its complement. What if we could check for the complement in O(1) instead of O(n)?
Approach 2: Hash Map (One Pass)
Intuition
Here's the key insight: for each element nums[i], we know exactly what value we need to complete the pair. It's target - nums[i]. The brute force approach searches for this complement by scanning the array. But what if we could check for it instantly?
A hash map gives us O(1) lookups. So the idea is: as we iterate through the array, we store each element's value and index in a hash map. Before storing the current element, we check whether its complement already exists in the map. If it does, we've found our pair. If not, we add the current element and move on.
The beautiful thing is that we only need a single pass. By the time we reach the second element of the answer pair, the first element is already in the map.
The hash map acts as a "memory" of elements we've already visited. Each element is processed exactly once: we either find its complement already in the map (meaning the pair is complete) or we add it to the map for future elements to find. The order of operations (check first, insert second) ensures we never match an element with itself.
This is a textbook example of the "complement search" pattern: instead of searching for two things simultaneously, fix one and search for the other.
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.