Two Sum — Hash Map Lookup

What does it solve?

Given an array nums and a target, return the indices of the two numbers that add up to it. The brute force checks every pair in O(N²); the hash-map approach does it in one pass.

Key insight: as you scan, for each number x the partner you need is target − x. Keep a hash map of every value seen so far → its index. Before inserting x, look up its complement. A lookup is O(1), so the whole scan is O(N). This "remember and look up" pattern is the core of Contains Duplicate, Group Anagrams, and countless others.

The core idea

// one pass, seen[value] = index
seen = {}
for i, x in enumerate(nums):
  need = target − x
  if need in seen:
    return [seen[need], i]
  seen[x] = i

Complexity

Time complexity

O(N)

A single pass over the array. Each element does one O(1) hash lookup and one O(1) insert, versus O(N²) for checking all pairs.

Space complexity

O(N)

In the worst case every value is stored in the map before the answer is found. Space traded for speed.

Examples & edge cases

Live animation — one pass, look up the complement in the map

current element x complement / probe just added to map pair found already processed

nums · target = —

Press Play to begin the scan…

Hash map — value → index

{ } empty

i = — need = — map size = — answer = —

Step — of —

current x

—

nums[i]

complement

—

target − x

map size

—

values stored

answer

—

index pair

Select an example and press Play to start.

✓ Done

Speed Medium

Step-by-step table

Step	i	x = nums[i]	need	in map?	Action	Map after

C++ implementation

two_sum.cpp

#include <bits/stdc++.h>
using namespace std;

// Return indices of the two numbers adding up to target
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];
        auto it = seen.find(need);
        if (it != seen.end())          // complement already stored
            return {it->second, i};
        seen[nums[i]] = i;             // remember this value
    }
    return {};                         // no pair sums to target
}

int main() {
    vector<int> nums = {2, 7, 11, 15};
    auto ans = twoSum(nums, 9);
    cout << ans[0] << " " << ans[1] << "\n"; // 0 1
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars