cf.completefrontend
ARRAYS & HASHING · CORE

Complement lookup

To find two values that combine into a target, store what you've seen and look up the missing partner of each new value.

Time O(n)Space O(n)6 practice problemsStep-through picture

The idea

Many problems ask for two items that fit together: two prices that add up to a gift card's value, two numbers whose difference is k. The brute-force way checks every pair, which takes O(n^2) time.

Complement lookup does it in one pass. For each number, work out the partner it would need: for a sum, that is target - nums[i]. This partner is called the complement. Then ask a hash map whether the complement was already seen. If it was, you found the pair. If not, store the current number so a later number can find it.

The code here returns the indexes of two numbers that add up to target, using a Map from each value to the index where it was seen.

An everyday example

Matching puzzle pieces from a pile

You're pulling puzzle pieces from a bag one at a time and laying them on a table, sorted by shape. Each new piece needs a partner with the opposite edge. Instead of trying it against every piece on the table, you look straight at the spot where its partner's shape would be. If the partner is there, you snap them together. If not, you put the new piece in its own spot for a later piece to find.

How the example maps to the code
In the exampleIn the code
The table of pieces you've laid outindexOf, a Map from value to index
The shape the partner must haveneed = target - nums[i]
Looking at the partner's spotindexOf.has(need)
Putting the new piece in its spotindexOf.set(nums[i], i)

From the slow way to complement lookup

  1. The obvious way to find two numbers that add up to target: try every pair. With n numbers there are n × (n - 1) / 2 pairs, so 10,000 numbers means about 50 million sums. The time grows with the square of the list's length.
  2. Look at one number nums[i] on its own. Only one partner value can work with it: target - nums[i]. So the inner loop isn't searching for "any number that fits". It's searching for one exact value, which is a lookup question, not a search.
  3. Exact lookups are what a hash map does in about constant time. If every number you've already passed is stored with its index, the whole inner loop turns into one has call: is the needed value among the numbers before me?
  4. The order of the two steps matters. Look up the complement first, then store the current number. Then a number can't pair with itself, and every pair is found when the loop reaches its later number. One pass, look up and then store: that loop is complement lookup.

How it works

  1. Create an empty Map called indexOf, from a value to the index where it was seen.
  2. Walk through nums with index i.
  3. Work out the complement: need = target - nums[i].
  4. If indexOf.has(need), an earlier number completes the pair: return [indexOf.get(need), i].
  5. Otherwise store the current number: indexOf.set(nums[i], i).
  6. If the walk ends without a match, return [].

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function findPair(nums, target) {
  2. const indexOf = new Map();
  3. for (let i = 0; i < nums.length; i++) {
  4. const need = target - nums[i];
  5. if (indexOf.has(need)) {
  6. return [indexOf.get(need), i];
  7. }
  8. indexOf.set(nums[i], i);
  9. }
  10. return [];
  11. }

How fast it is

TimeO(n)
Extra memoryO(n)

Each number costs one lookup and one insert, both constant time on average. The map can end up holding every number.

  • Best caseO(1)

    The first two numbers already add up to target, like [3, 7, ...] with target = 10: two lookups and it returns.

  • Average caseO(n)

    The pair's later number is somewhere in the middle, so about half the list is read, each step in constant time.

  • Worst caseO(n)

    No pair exists, or the pair's later number is the last item. All n numbers are looked up and stored.

Common mistakes

  • Storing nums[i] before looking up need, so a single 5 pairs with itself when target is 10.
  • Filling the whole map first and then looking up, which also lets an item match itself unless you compare indexes.
  • Sorting the array to use two pointers when the problem asks for the original indexes.
  • Counting pairs with a set instead of a count map, which undercounts when values repeat.

When to use it

Look for these clues in a problem:

  • The problem asks for two items whose sum, difference, or product hits a target.
  • The input is not sorted, or sorting would lose the original indexes you need to return.
  • You need to count pairs that fit together, such as pairs whose sum is a multiple of k.
  • A brute force would compare every pair.

Check yourself

Answer each one in your head first, then open it.

Why can't nums = [5] with target = 10 return [0, 0]?

The code looks up need before storing nums[i], so when 5 looks for 5, the map is still empty.

For nums = [1, 9, 9] and target = 10, which pair is returned?

[0, 1]. At i = 1, need is 1, which is stored at index 0, so the loop returns before reaching the second 9.

Why does the map go from value to index, and not from index to value?

Because the question at each step is "where is the value need?". The map must be keyed by what you look up, which is the value.

At most how many map operations does the code do on n numbers?

About 2n: one has per number and one set per number that doesn't complete a pair. Each is about constant time, so the total is O(n).

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 6 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one rule: at the top of step i, indexOf holds every value from indexes 0 to i - 1, each mapped to an index where it appears. It starts empty, which is right for i = 0, and each step that doesn't return stores nums[i], so the rule carries over to step i + 1. When a value repeats, set overwrites its index with the later one, which is still a valid earlier index.

Take any pair of indexes j < i with nums[j] + nums[i] = target. Then nums[j] equals need at step i, and by the rule it's in the map when the loop reaches i. So the loop can't pass i without returning a pair, and it returns at the first i that completes any pair. The index it returns is always smaller than i, so a number never pairs with itself.

The loop runs at most n times. If it ends without returning, no i found its partner among the numbers before it, which means no pair exists, so returning [] is correct.

Going deeper

3 more ideas

Why checking before storing matters

The code looks for the complement before adding nums[i] to the map. That way a number can never pair with itself: with target = 10 and nums[i] = 5, the map only holds earlier numbers, so it finds a 5 only if a different 5 came before. And because every pair (j, i) with j < i is checked when the loop reaches i, no pair is missed.

Other kinds of complement

The same idea works for any rule where one value decides its partner. For a difference of k, look up nums[i] - k and nums[i] + k. For sums divisible by k, use remainders: a number with remainder r needs a partner with remainder (k - r) % k. To count pairs instead of finding one, store how many times each value was seen and add that count at each step.

Cost compared with other ways

Each step is one has and one set, so the time is O(n) and the map uses O(n) space. Checking every pair is O(n^2) with no extra space. Sorting first and walking two pointers inward is O(n log n) with little extra space, but it loses the original positions unless you sort indexes.

Work it by hand

Every step in a table, with why

Find two numbers that add up to 10. The answer uses the value 5 twice, so the trace shows why storing after the lookup is safe.

nums = [5, 14, 2, 9, 5], target = 10

Stepinums[i]needindexOf beforeWhat happensWhy
1055{}Not found: store 5 -> 0The map is empty, so this 5 can't pair with itself. That is the point of looking up before storing.
2114-4{5: 0}Not found: store 14 -> 1need can be negative. It's just a key to look up, and no stored number is -4.
3228{5: 0, 14: 1}Not found: store 2 -> 2No 8 has been seen, so 2 is stored for a later number to find.
4391{5: 0, 14: 1, 2: 2}Not found: store 9 -> 3No 1 has been seen either. Four numbers are stored now.
5455{5: 0, 14: 1, 2: 2, 9: 3}Found: return [0, 4]This second 5 needs a 5, and the first one is stored at index 0. The pair is found when the loop reaches its later number.

It returns [0, 4], because nums[0] + nums[4] is 5 + 5 = 10. It took 5 lookups instead of the 10 pairs a brute force would check.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Complement lookupO(n)O(n)The list is unsorted and you need the original indexes, or just the fastest single pass.
Sort, then two pointersO(n log n)O(1)You only need the values, can sort in place, and want no extra memory. It also handles "closest sum" questions.
Binary search for each partnerO(n log n)O(n)The list is already sorted and you'll also ask other range questions of it. Two pointers is usually simpler.
Check every pairO(n²)O(1)Tiny lists, or as the first idea you say out loud before improving it.

Extra memory: O(n): the map can end up holding every number. That's the price for turning the inner loop into one lookup.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Complement lookup and the other approaches, on a scale where each line up is 10 times more steps.
  • Complement lookup O(n)
  • Sort, then two pointers, Binary search for each partner O(n log n)
  • Check every pair O(n²)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Complement lookup101,0001 million
Sort, then two pointers339,96620 million
Binary search for each partner339,96620 million
Check every pair1001 million1 trillion

Inputs that need care

5 tricky inputs
An empty list or one number: [] or [7]
There is no pair. The loop runs 0 or 1 times and returns [].
A pair made of two equal values: nums = [6, 6], target = 12
At i = 0 the map is empty, so 6 is stored. At i = 1, need is 6, found at index 0. It returns [0, 1].
A single number that is half the target: nums = [6], target = 12
The lookup happens before the store, so the map is empty when 6 looks for 6. It returns [], which is right: one 6 can't be used twice.
Many copies: nums = [4, 4, 4, 6], target = 10
Each 4 overwrites the stored index, so 4 -> 2 is in the map when 6 arrives. It returns [2, 3]. Store only if the key is missing if you need the earliest index.
Negatives and zero: nums = [-3, 0, 13], target = 10
Nothing special is needed. At i = 2, need is -3, stored at index 0, so it returns [0, 2].

Variations and follow-ups

Twists interviewers add

Count every pair

Store how many times each value was seen instead of its index. At each number, add the count of need to the answer, then add 1 to the count of the current number. Repeated values are counted correctly this way.

Three numbers that add up to a target

Fix the first number, then run complement lookup on the numbers after it with target - nums[a]. That is n passes of O(n) each, O(n²) in all. Sorting first and using two pointers has the same time and makes skipping duplicates easier.

Pairs across two lists

To match items from two lists, like orders and payments that should add up to a total, build the map from one list, then look up each item of the other. That costs O(n + m) and the map holds only the first list.

Closest sum instead of exact

A hash map only answers "is this exact value there?", so it can't find the nearest sum. For "closest to target", sort the numbers and move two pointers inward, keeping the best sum seen.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from words like "two numbers that add up to", "pair with difference k", "return their indexes", or "in one pass".
  • Explain it with one sentence: "for each number I know exactly which partner it needs, so I ask a map whether that partner came earlier."
  • Test by hand: a pair made of two equal values, a single value that is half the target, and a list with no pair.
  • The usual follow-up is "what if the array is sorted?". Answer: use two pointers from both ends, which needs O(1) extra space. If asked for all unique pairs, sort first and skip equal neighbors so each pair is reported once.

Where frontend code uses it

The same idea in real UI code
  • A cart page suggesting one item that tops the order up to exactly the free-shipping amount: look up threshold - total in a map of prices.
  • Reconciling payments: matching each refund with the charge it cancels by looking up its opposite amount.
  • Pairing opening and closing events by id in a performance trace, such as mark start and end entries.

Related algorithms