Back to solutions

Two Sum

EasyArrays

Return the indices of the two numbers in an array that add up to a target.

Open problem
Constraints
  • 2 <= n <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • Exactly one valid pair exists

Hash map (one pass)

Time O(n)Space O(n)

As you scan the array, remember every value you have seen along with its index. For the current value x, the partner you need is target - x. If that partner is already in the map you have found the pair; otherwise record x and move on. Each lookup is O(1), so one pass solves it.

Key terms
complement:
The value you still need to reach the target. For value x it is target - x.
hash map:
A dictionary that maps keys to values with average O(1) insert and lookup. Here it maps each number to the index where it appeared.
one pass:
Solving the problem in a single left-to-right scan instead of nested loops.
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> seen; // value -> index
    for (int i = 0; i < (int)nums.size(); i++) {
        int need = target - nums[i];
        if (seen.count(need)) return {seen[need], i};
        seen[nums[i]] = i;
    }
    return {};
}
Step by step
  1. Create an empty hash map `seen` that will map each value to its index.
  2. Loop over the array with index i and value nums[i].
  3. Compute need = target - nums[i], the complement that would complete the pair.
  4. If need is already a key in `seen`, the pair is (seen[need], i) return it.
  5. Otherwise store seen[nums[i]] = i so future elements can find this one.
  6. The driver reads n, target, and the array from stdin, calls the function, and prints the two indices.