DSA PatternsHashingeasy12 min read

Two Sum Pattern — Value to Index Map

The hash map turns a brute-force O(n²) pair search into a single O(n) pass. We build the idea from a cloakroom story, prove it with a frame-by-frame trace, and extend it to three-sum, four-sum, and complement-pairing problems.

#hashmap#two-sum#complement#pairing#beginner#interview

Table of contents

Before we start

By the end of this page you will be able to:

See why storing "what you've already seen" in a hash map makes the second scan instant.
Explain out loud why each number only needs to ask "is my complement already here?" — and never needs to look forward.
Recognise this complement-pairing skeleton in two-sum, four-sum, and k-diff pair problems.

Stop at every Pause & Think box.

Picture this first (no code yet)

A real-life story

A cloakroom at a party uses numbered receipts. When you hand in your coat, you get receipt 7. Target tonight: pair up every coat worth exactly ₹50 total with another coat.

An old attendant checks every pair manually — she pulls coat 7, then checks coat 1, coat 2, coat 3… all the way to coat 43 (7 + 43 = 50). O(n²) effort.

A smarter attendant does this: the moment coat 7 arrives, she thinks — "7's complement is 43 (50 − 7). Is receipt 43 already hanging on the board?" She glances at the board in one second. If yes — pair found. If no — she pins receipt 7 on the board and moves to the next coat.

She never looks forward. She never re-checks old coats. Every coat gets one glance at the board; every coat gets pinned once. Done in a single pass.

The board is the hash map. The question "is my complement already here?" is the single O(1) lookup. That's the entire Two Sum pattern.

The actual problem

Given an array of integers and a target sum, find the indices of the two numbers that add up to the target. Assume exactly one valid answer exists.

input  : nums = [2, 7, 11, 15], target = 9
output : [0, 1]   because nums[0] + nums[1] = 2 + 7 = 9

First, the slow way (so you feel the pain)

Check every pair:

for i in range(n):
    for j in range(i + 1, n):
        if nums[i] + nums[j] == target:
            return [i, j]

n = 10,000    →  ~50,000,000 pair checks
n = 100,000   →  ~5,000,000,000 pair checks

O(n²). For large inputs, this is unusable. We need O(n).

The turning point

Rearrange the equation. Instead of checking nums[i] + nums[j] == target, ask:

Is (target - nums[i]) somewhere in the array?

target - nums[i] is called the complement of nums[i].

Pause & think

For nums = [2, 7, 11, 15] and target = 9:

When you look at 2 (index 0), what is its complement? Where would you look it up — and how fast?

When you look at 7 (index 1), what is its complement? Has it been seen yet?

Complement of 2 is 7. At the moment you read index 0, you haven't seen 7 yet — it's still ahead. So you pin {2: 0} on the board (value → index) and move on.

Complement of 7 is 2. You glance at the board — 2 is there at index 0. Pair found: [0, 1].

The order matters: pin first, ask second — or rather, ask first, then pin. Asking before pinning prevents pairing a number with itself.

The one idea to remember

The entire pattern in one sentence

For each number, check if its complement (target - num) is already in the hash map — if yes, you found the pair; if no, store this number's index in the map and continue.

Watch it happen, frame by frame

nums = [3, 2, 4], target = 6. Map starts empty.

i=0: num=3. complement=6-3=3. Is 3 in map? No.  Pin {3:0}.  map={3:0}
i=1: num=2. complement=6-2=4. Is 4 in map? No.  Pin {2:1}.  map={3:0, 2:1}
i=2: num=4. complement=6-4=2. Is 2 in map? YES → index 1.  Return [1, 2] ✓

Pause & think

Cover the trace below. Try nums = [3, 3], target = 6. What happens at each step? Does it correctly return [0, 1] and not [0, 0]?

Check your trace

i=0: num=3. complement=3. Is 3 in map? No.  Pin {3:0}.  map={3:0}
i=1: num=3. complement=3. Is 3 in map? YES → index 0.  Return [0, 1] ✓

It correctly returns [0, 1] because we check the map before pinning the current index. When we process the second 3, the map holds the first 3 at index 0 — not the current one.

Now, the code — line by line

def twoSum(nums, target):
    seen = {}                              # value → index  (the cloakroom board)

    for i, num in enumerate(nums):
        complement = target - num          # what partner does this number need?

        if complement in seen:             # is the partner already on the board?
            return [seen[complement], i]   # yes — return both indices

        seen[num] = i                      # no — pin this number on the board
                                           # (pin AFTER checking to avoid pairing with self)
    return []

Line by line mapped to the cloakroom:

seen = {} — empty board at the start of the night.
complement = target - num — "what receipt number would complete my pair?"
if complement in seen: — one glance at the board.
return [seen[complement], i] — the board remembers the index; return both.
seen[num] = i — pin this receipt after checking, so a number never pairs with its own entry.

Time: O(n) — one pass, O(1) hash map operations each step. Space: O(n) — the map stores at most n entries.

Why checking before pinning matters

Suppose nums = [6] and target = 12. Complement of 6 is also 6. If we pinned first and then checked, we'd find 6 in the map and return [0, 0] — but index 0 and index 0 is the same element, not two distinct elements. Checking before pinning ensures we only pair with previously seen elements.

When should I reach for this? (the trigger list)

Reach for the complement hash map when:

Asked to find two numbers (or indices) summing to a target.
You want O(n) instead of O(n²) — and sorting would destroy index information.
The array has no sorted order guarantee (otherwise consider two-pointer).
The problem says "find the pair/triplet/indices" — not just "does it exist" (for existence-only, a set suffices).
You see variants: "k-diff pairs," "complement in another array," "four-sum using two maps."

Two Sum vs. Two Pointers — which to use?

Two Pointers (pattern 1.01): array is already sorted, you only need the values (not original indices), O(1) space.

Hash Map (this pattern): unsorted array, or you need original indices, O(n) space.

If you're allowed to sort and don't need indices: two pointers. Otherwise: hash map.

The same trick in five disguises

Disguise 1 — Two Sum (return boolean, not indices)

A set suffices — no need to track indices:

def hasTwoSum(nums, target):
    seen = set()
    for num in nums:
        if target - num in seen:
            return True
        seen.add(num)
    return False

Disguise 2 — Two Sum II (sorted array)

If the array is sorted and you only need values, use opposite-end two pointers (O(1) space). Only use hash map if you need indices in original positions.

Disguise 3 — 3Sum using Two Sum as a subroutine

Fix one element nums[i], then run Two Sum on the rest looking for target - nums[i]:

def threeSum(nums, target):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue                           # skip duplicate anchors
        seen = {}
        need = target - nums[i]
        for j in range(i + 1, len(nums)):
            complement = need - nums[j]
            if complement in seen:
                result.append([nums[i], complement, nums[j]])
            seen[nums[j]] = j
    return result

Disguise 4 — 4Sum II (LC #454): sum from four arrays

Count pairs (a+b) from arrays A and B, store in a map. Then for each pair (c+d) from C and D, look up -(c+d). O(n²) total instead of O(n⁴):

def fourSumCount(A, B, C, D):
    ab = {}
    for a in A:
        for b in B:
            ab[a + b] = ab.get(a + b, 0) + 1

    count = 0
    for c in C:
        for d in D:
            count += ab.get(-(c + d), 0)
    return count

Disguise 5 — K-diff Pairs (LC #532)

Count pairs where |nums[i] - nums[j]| == k. Convert to: for each num, is num + k (or num - k) in the set? Handle k=0 separately (need duplicates).

def findPairs(nums, k):
    from collections import Counter
    freq = Counter(nums)
    count = 0
    for num in freq:
        if k == 0:
            if freq[num] > 1: count += 1    # duplicate exists
        else:
            if num + k in freq: count += 1  # complement exists
    return count

Level up — Two Sum variants in streams (online algorithm)

When numbers arrive one at a time and you must answer after each: maintain a set of seen values. When x arrives, check if target - x is in the set. If yes — found. Then add x to the set. This is the exact same algorithm working in streaming mode — the hash map naturally handles it.

Traps that catch beginners

Watch out for these

Pinning before checking. Doing seen[num] = i before if complement in seen means a number can pair with itself. Always check first, then pin.
Using a set when indices are needed. A set only stores values, not indices. If the problem asks for index positions, use a dict ({value: index}).
Assuming exactly one answer. The basic Two Sum guarantees one answer. Variants like "count all pairs" or "find all unique pairs" need extra handling for duplicates.
Confusing the complement. complement = target - num — not target + num, not num - target. Write it out explicitly if you're unsure.

Bug	Fix
Pin before check → self-pairing	Always check `complement in seen` before `seen[num] = i`
Using set when index needed	Use `dict` mapping value → index
Missing duplicate pairs	Use `Counter` or frequency map to count appearances

Say it like a pro (interview one-liner)

"I'll use a hash map to store each number's index as I scan. For every number, I compute its complement — target minus current — and check if the complement is already in the map. This is one O(1) lookup per element, giving O(n) total time and O(n) space. I check before storing to avoid pairing a number with itself."

Remember this forever

Two Sum — Complement Hash Map

For each num: check if target - num is in the map (O(1)). If yes → pair found. If no → store {num: index} and continue.

Key habit: check before storing — prevents self-pairing

Two Sum vs Two Pointers: need indices OR unsorted → hash map · sorted + only values needed → two pointers

Cost: O(n) time, O(n) space

Skeleton: for i, num in nums: if target-num in seen: return answer; seen[num]=i

Check yourself

Why do we check the map before storing the current number — not after?

If we stored first, then checked, a number could "pair with itself." For example, nums = [6] with target = 12: we'd store {6: 0}, then find complement 6 in the map and return [0, 0] — the same index twice. Checking first means we only match with numbers from previous iterations, never the current one.

When would you use a set instead of a dict for Two Sum?

When the problem only asks whether a pair exists (boolean answer), not which indices they are at. A set stores values in O(1), which is enough for existence checking. A dict is needed when you must return the indices of the two numbers.

How does Two Sum extend to Three Sum using this pattern?

Fix one element nums[i] (the "anchor"). The problem reduces to: find two numbers in the remaining array that sum to target - nums[i]. That's exactly Two Sum on a subarray. Run it for each anchor. Total time: O(n²) — one outer loop (fix anchor) × O(n) inner Two Sum.

What's the tradeoff between hash map Two Sum and two-pointer Two Sum?

Hash map: works on unsorted arrays, preserves original indices, O(n) space. Two pointer: requires sorted order, O(1) space, but sorting destroys original indices (unless you zip with original indices first). If you need indices in original positions: always hash map. If array is sorted and values suffice: two pointers.

Practice problems

Problem	Difficulty	What to notice	Link
Two Sum	Easy	Core pattern — check complement before storing	LC #1
Two Sum II (sorted)	Easy	Sorted → two pointers O(1) space; or hash map if indices needed	LC #167
K-diff Pairs in an Array	Medium	k=0 needs frequency≥2; k>0 check num+k in set	LC #532
4Sum II	Medium	Build ab-sum map; look up -(c+d)	LC #454
Two Sum IV (BST)	Easy	Inorder traversal to get sorted array, then two pointers	LC #653

Next up: Frequency Counting — where the hash map doesn't pair numbers but tallies them, turning "who appears most?" into a single pass.

PreviousSubarray Counting — Prefix Sum + Hash Map NextFrequency Counting

Back to all topics