Two Sum
Find the two indices in an unsorted array whose values add up to the target.
Problem Summary
Original task summary for this archive page. The official LeetCode prompt is linked in the header instead of being mirrored here.
You are given an unsorted array and a target value. Find the two positions whose values add up exactly to the target.
The main constraints are what make this interesting: you need indices, the input is not sorted, and there is exactly one valid pair.
Recognition Pattern
How to notice the underlying interview pattern before writing code.
This is the classic complement lookup with a hash map pattern.
In interviews, recognize it when:
you need a pair whose values satisfy a direct equation such as \(a + b = target\)
the array is unsorted, so two pointers are not immediately available
the problem asks for indices or original positions
Key Idea
The main invariant or observation that makes the clean solution work.
As you scan from left to right, each number asks a simple question: have I already seen the value that completes the target?
If the current value is \(x\), the needed complement is \(target - x\). A hash map lets us answer that question in \(O(1)\) average time. If the complement was seen earlier, we already have the answer. Otherwise, store the current value and its index for later numbers.
Step-by-step Reasoning
How to move from the obvious brute-force idea to the interview-ready solution.
The brute-force approach checks every pair of indices. That works, but it costs \(O(n^2)\), which is unnecessary for such a direct equality test.
Sorting is tempting because it enables two pointers, but it complicates index recovery and adds work that the problem does not need.
The better observation is that each number only cares about one missing value. That turns the problem from search all pairs into answer one lookup per element. A hash map is exactly the right tool for that shift.
One subtle detail matters: check for the complement before inserting the current number. That guarantees the answer uses two distinct indices.
Complexity
Time and memory costs for the implementation shown below.
Time: \(O(n)\) average
Space: \(O(n)\)
C++ Solution
The exact repository source used for this LeetCode solution page.
#include <unordered_map>
#include <vector>
class Solution {
public:
std::vector<int> twoSum(std::vector<int>& nums, int target) {
std::unordered_map<int, int> indexByValue;
for (int index = 0; index < static_cast<int>(nums.size()); ++index) {
const int value = nums[index];
const int complement = target - value;
auto it = indexByValue.find(complement);
if (it != indexByValue.end()) {
return {it->second, index};
}
indexByValue[value] = index;
}
return {};
}
};
Common Pitfalls
Real implementation mistakes that show up often in interviews and submissions.
Inserting the current number before checking its complement can accidentally reuse the same element when \(target = 2 \cdot nums[i]\).
Returning the values instead of the indices misses what the problem actually asks for.
Overwriting indices carelessly can make duplicate-heavy cases harder to reason about.
Variants / Follow-ups
Nearby problems and the next generalization to learn once this pattern is stable.
The next step is Two Sum II, where the array is already sorted and two pointers become the cleanest tool.
This same complement idea also reappears inside larger problems such as 3Sum, where you fix one value and solve a two-number subproblem on the remaining suffix.
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.