Coding Interview Patterns Module 3 – Arrays and hashing

Complement lookup: pairs in one pass

Find two values that add up to a target in one pass: look up each item's complement in a hash map before storing it, the idea behind two sum.

Beginner
25 minutes
Examples run with Python 3.14.8, Pyodide 314.0.7, Node.js 24.21.0, quickjs 0.32.0, Java 25, Clang 21.0.0 and Go 1.27.1
By MySmartCoPilot

Free: The problem: two items for one voucher · One pass: look up the partner, then store the item · Practise: the voucher problem. With a pass: 3 in-depth parts and 3 interview answers, about 17 minutes.

What you will learn

Find a pair with a target sum in one pass with a hash map, and say why it takes O(n) time
Avoid pairing an item with itself by looking up its partner before storing it
Select the pair a problem ranks first by keeping the first position of each value
Count pairs correctly when values repeat, and pairs whose values differ by k
Choose between a hash map, sorting with two pointers and the brute force for given limits

Before you start

Hash map patterns: lookup, count, group

What you’ll learn · Before you start

What you will learn

Find a pair with a target sum in one pass with a hash map, and say why it takes O(n) time
Avoid pairing an item with itself by looking up its partner before storing it
Select the pair a problem ranks first by keeping the first position of each value
Count pairs correctly when values repeat, and pairs whose values differ by k
Choose between a hash map, sorting with two pointers and the brute force for given limits

Before you start

Hash map patterns: lookup, count, group

On this page

Complement lookup finds two items that fit together, such as two of 100,000 menu prices that add up to a voucher’s value, in one pass: about 10⁵ lookups, where trying every pair takes about 5 × 10⁹ sums. For each item it works out the one value that would complete the pair, its complement: The one value that completes a pair with the current item, such as target − x when two values must add up to a target. Complement lookup asks a hash map whether an earlier item had it. (value − price for a sum), and asks a hash map whether an earlier item had that value. If one did, the pair is found; if not, the item goes into the map and the pass moves on. One lookup and at most one insertion per item make the search O(n) on average, where trying every pair costs O(n²). The problem is widely known as two sum; here it comes in an original form, with its limits, its brute force and the one-pass idea worked through.

The problem: two items for one voucher

The problem

A canteen’s menu lists the prices of its items, prices[0..n − 1], in menu order, and prices may repeat. A voucher worth exactly value must be spent in full on two different items. Return the positions (i, j), with i < j, of two items whose prices add up to value, or (−1, −1) if no two do. If several pairs fit, return the one whose second item comes first on the menu, and among those the one whose first item comes first. Limits: 0 ≤ n ≤ 100,000, 1 ≤ prices[i] ≤ 10⁹ and 2 ≤ value ≤ 2 × 10⁹.

Three examples, and every program below is run on each of them:

prices = [70, 25, 90, 55, 35, 105] and value = 125 give (0, 3). Two pairs fit, 70 + 55 and 90 + 35, and the first one is completed earlier: its second item sits at position 3, the other’s at position 4.
prices = [60, 15, 45] and value = 120 give (−1, −1). Two items of 60 would do, but the menu has only one.
prices = [50, 30, 50] and value = 100 give (0, 2): two different items may have the same price.

The brute force: every pair

Try every pair, with the second item j in the outer loop and the first item i < j in the inner loop, both in menu order, and return the first pair that fits. That loop order makes the first pair found the one the problem ranks first. The brute force is plainly correct, which makes it the reference to test faster code against, but on a menu where no pair fits it adds up all n(n − 1)/2 sums:

Every pair, and how many sums that takes Python · brute/voucher_brute.py

"""Two menu items for one voucher, by brute force: every pair, in the order the problem ranks the answers."""
import time


def voucher_pair_brute(prices, value):
    """Positions (i, j), i < j, of two items that cost exactly value together, or (-1, -1).

    j grows in the outer loop and i in the inner one, so the first pair found is the one whose second item comes
    first on the menu, and among those the one whose first item comes first: the pair the problem asks for.
    """
    for j in range(len(prices)):
        for i in range(j):
            if prices[i] + prices[j] == value:
                return (i, j)
    return (-1, -1)


print(voucher_pair_brute([70, 25, 90, 55, 35, 105], 125))  # 70 + 55
print(voucher_pair_brute([60, 15, 45], 120))  # only one item costs 60
print(voucher_pair_brute([50, 30, 50], 100))  # two different items that both cost 50

# The slowest case: no pair fits, so every pair is tried. Even prices never add up to an odd value.
for n in (1_000, 2_000):
    prices = [2 * k + 2 for k in range(n)]
    start = time.perf_counter()
    assert voucher_pair_brute(prices, 1_000_001) == (-1, -1)
    ms = (time.perf_counter() - start) * 1000
    print(f"n = {n:,}: {n * (n - 1) // 2:,} sums in {ms:,.0f} ms")

per_sum = ms / 1000 / (n * (n - 1) // 2)  # seconds per sum, from the run with n = 2,000
n = 100_000
print(f"n = {n:,}: {n * (n - 1) // 2:,} sums, about {n * (n - 1) // 2 * per_sum:,.0f} s at that speed")

Output

(0, 3)
(-1, -1)
(0, 2)
n = 1,000: 499,500 sums in 16 ms
n = 2,000: 1,999,000 sums in 77 ms
n = 100,000: 4,999,950,000 sums, about 193 s at that speed

This output changes from run to run: the times depend on the computer and on what else it is doing

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 voucher_brute.py

Doubling the menu from 1,000 to 2,000 items multiplies the sums by four, exactly. At the limit of 100,000 items that is about 5 × 10⁹ sums. With the rough budgets of the lesson on constraints, about 10⁸ simple steps fit in a second of C++ and about 10⁷ in CPython, so the brute force needs close to a minute of C++ and several minutes of Python, against a time limit of about a second.

What to notice

For each item, exactly one price can complete the pair: value − price. The brute force asks every earlier item, one comparison at a time, whether it has that price. A hash map that holds the earlier prices answers the same question in a single lookup, O(1) on average, and that turns the whole inner loop into one step. Sorting the prices and moving two pointers inwards is the other common way to find a fitting pair.

One pass: look up the partner, then store the item

The one-pass search keeps a map from each price it has read to the first position where that price appeared, and takes the items in menu order:

Work out the partner of the current price: need = value − price.
If need is in the map, return (map[need], j).
Otherwise store price → j, unless that price is in the map already, and go on to the next item.
If the menu ends first, return (−1, −1).

Two details carry the whole problem. Look up before you store. The map then holds only items before position j, so an item at exactly half the value can never pair with itself, which is the trap of the second example. Keep the first position of a price. A later item with the same price would complete the same pair, but the problem ranks the pair with the earlier first item higher. Each item costs one lookup and at most one insertion, so the pass takes O(n) time on average and O(n) extra memory for the map.

One pass over the menu, partner first

Text description of the diagram

The chart is a loop that runs once for each item of the menu, in menu order.

Take the next item: its price at position j.
Work out its partner: need = value − price.
Ask whether need is in the map. If yes, the answer is the pair (map[need], j), and the search stops.
If not, store price → j in the map, unless the price is already there, and take the next item: back to step 1 with the next j.

When no items are left, the answer is (−1, −1): no two items cost exactly the voucher's value.

A worked example

The first example, one row per item; the last column says what happens to the map:

j	price	need	then
0	70	55	store 70 → 0
1	25	100	store 25 → 1
2	90	35	store 90 → 2
3	55	70	70 found: `(0, 3)`

The pair 90 + 35 is never reached. The search stops at the first item that completes a pair, and the rows before it prove that no earlier item could complete one. Step through the same rows, one item at a time:

Interactive · step by step One pass over the menu, partner first Step through the menu. Each item works out its partner, asks the map for it, and only then stores its own price.

The drawing shows the whole scene; its 7 steps are listed below.

Every step as text

The empty map. The menu is [70, 25, 90, 55, 35, 105] and the voucher is worth 125. The map from each price read so far to its first position starts empty.
Position 0. Position 0 costs 70, so its partner must cost 125 − 70 = 55. The map is empty, so no earlier item costs 55.
Store 70. Only now is 70 stored, with its position 0. Looking up before storing means the map never holds the item that is asking.
Position 1. 25 needs 125 − 25 = 100, which no earlier item costs, so 25 is stored with position 1.
Position 2. 90 needs 35. No earlier item costs 35 either, because 35 sits at position 4, after 90, so 90 is stored with position 2.
Position 3. 55 needs 70, and the map holds 70 at position 0. The pair (0, 3) is found in the lookup, before 55 is stored.
The search stops. The first item that completes a pair ends the search. The pair 90 + 35 at positions 2 and 4 is never reached, and the rows before position 3 show that no earlier item could complete one.

Checkpoint

Check: The brute force and its cost at the limits · Look up the partner, then store the item

Question 1 of 3 The brute force runs on a menu of 10,000 items where no two prices fit the voucher. How many sums does it add?
Type a number.
Your answer sums

A hint

It adds every pair once, n(n − 1)/2 of them.

Show the answer: Question 1 of 3

Answer: 49995000 sums

10,000 × 9,999 / 2 = 49,995,000 sums. Ten times the items makes about a hundred times the sums, which is why 100,000 items need about 5 × 10⁹.
Question 2 of 3 A version stores each price before it looks up the partner. What does it return for [60, 15, 45] with a voucher of 120?
Choose one answer.

(1, 2) (−1, −1) (0, 2) (0, 0)

Show the answer: Question 2 of 3

Answer: (0, 0)

Looking up before storing means the map holds only earlier items, so a price at exactly half the voucher can never pair with itself. Storing first breaks the second example of the problem.
Question 3 of 3 What does the one-pass search return for [40, 40, 60, 40] with a voucher of 100?
Choose one answer.

(1, 2) (0, 1) (2, 3) (0, 2)

Show the answer: Question 3 of 3

Answer: (0, 2)

Keeping the first position of each price returns the pair whose first item comes first, (0, 2), the one the problem ranks first among the pairs completed at position 2.

Practise: the voucher problem

Python Online Compiler Paste the brute force and time it on a menu as large as you like, then try the trace above by hand.

These questions cover the problem, its brute force and the one pass, weakest idea first.

The one-pass search in 14 languages, with its proof Pro: opens with a Pro, Premium or Ultimate pass

The search fits in a dozen lines in every language, and each language answers “is this key in the map?” in its own way. Below, the code runs in 14 languages with recorded output, an invariant proves that the first pair it finds is the pair the problem ranks first, and a stress test: A check that runs a fast solution and a trusted brute force on many small random inputs and stops at the first input on which they disagree, which then becomes a test case. More in “From brute force to optimal: the usual moves” catches two slips.

In this part:

The code in 14 languages
The invariant that proves the first pair found is right
Two slips, caught by a stress test

1 diagram · 3 runnable examples (Go, Python) · about 11 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a pass I have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Counting pairs when prices repeat, and pairs with a gap Pro: opens with a Pro, Premium or Ultimate pass

Many versions of the problem ask how many pairs fit rather than which one. The map then stores counts instead of positions, the answer can outgrow a 32-bit integer, and a gap of k needs two lookups per item.

In this part:

Counting with a frequency map, traced
How large the count gets, with numbers
Pairs that differ by k, and the trap when k is 0
Count the pairs whose amounts differ by k
- Results of the sample tests

2 runnable examples (Python) · 1 exercise with sample tests · about 6 minutes

Opening this part with your pass…Pro part. It opens with the same pass as the part above.

Hash map, sorting or two pointers: choosing with measured numbers Pro: opens with a Pro, Premium or Ultimate pass

A hash map is the usual answer, but not the only one, and interviewers often ask for the others. Below, the alternatives are timed on the same menus and set side by side, and the edge cases, variants and follow-up questions that come next are answered.

In this part:

Measured: one pass against sorting on 100,000 prices
The trade-offs side by side
Edge cases and common bugs
Variants, with answers
Follow-up questions, answered

1 runnable example (Python) · about 8 minutes

Opening this part with your pass…Pro part. It opens with the same pass as the part above.

Interview questions

Fresher to mid · Warm-up

In the one-pass pair search, why must each item look up its partner before the item itself goes into the map?

Because the map must hold only the items before the current one. If an item were stored first, an item worth exactly half the target would find itself in the map and be reported as a pair of one item: [60, 15, 45] with a target of 120 would give (0, 0) instead of no pair. Looking up first means that any partner the map returns sits at an earlier position, so the pair is always two different items. Two different items with the same value still pair correctly, because the first is stored and the second finds it.
Fresher to mid

An array holds 10⁶ integers, most of them repeated. Count the index pairs i < j whose values add up to a target T. What do you store while scanning, what is the largest possible answer, and which integer type must hold it in Java or C++?

Model answer, Pro. Model answers open with any pass; prices are in the notice on this page. First step and follow-ups
Mid to senior

Readings arrive as an endless stream of integers between 0 and 10⁶. After each reading you must say whether any two readings so far add up to exactly T, using at most 1 MB of memory. What do you store, and what does each answer cost?

Model answer, Pro. First step and follow-ups
Fresher to mid

A colleague's function counts the index pairs whose values differ by exactly k. It returns twice the right answer when k is 0 and is correct otherwise. What is the likely bug, how do you fix it, and which tests would have caught it?

Model answer, Pro. First step and follow-ups

Key takeaways

One map lookup per item replaces the inner loop of the brute force: the only partner a price can have is value − price.
Look up before you store, so the map holds only earlier items and no item pairs with itself.
Keep the first position of each price when the problem ranks pairs by their first item.
One pass costs O(n) time on average and O(n) memory, against n(n − 1)/2 sums for the brute force: about 5 × 10⁹ at n = 100,000.

Terms in this lesson

complement: The one value that completes a pair with the current item, such as target − x when two values must add up to a target. Complement lookup asks a hash map whether an earlier item had it.

References

Built-in types: mapping types (dict), dict.setdefault() (Python Software Foundation)
collections: Counter and defaultdict (Python Software Foundation)
tracemalloc: trace memory allocations (Python Software Foundation)
ECMAScript language specification: Map objects (Ecma International (TC39))
Number.MAX_SAFE_INTEGER (MDN Web Docs)
Java SE 25 API: Map (get, putIfAbsent) (Oracle)
Java SE 25 API: HashMap (Oracle)
std::unordered_map::try_emplace (cppreference.com)
std::unordered_map::operator[] (cppreference.com)
The Go Programming Language Specification: index expressions (The Go Authors)

Report a problem with this lesson

In this module: Arrays and hashing

Hash map patterns: lookup, count, group Free lesson, Pro answers: 30 minutes
Complement lookup: pairs in one pass Free core, Pro depth: 8 of 25 minutes free
Frequency maps: checking a valid anagram Free intro, Pro: 3 of 15 minutes free
Grouping with canonical keys Free intro, Pro: 4 of 15 minutes free
Sets for consecutive runs Free intro, Pro: 3 of 15 minutes free
Product of all others: prefix and suffix passes Free intro, Pro: 5 of 20 minutes free
Majority vote in O(1) space Free intro, Pro: 5 of 20 minutes free
Cyclic placement and in-place marking Free intro, Pro: 4 of 25 minutes free
Encoding lists of strings safely Free intro, Pro: 4 of 20 minutes free
Knowing what to track in one pass Free intro, Pro: 4 of 20 minutes free

Your country

Complement lookup: pairs in one pass

What you will learn

Before you start

What you will learn

Before you start

The problem: two items for one voucher

The brute force: every pair

What to notice

One pass: look up the partner, then store the item

A worked example

Practise: the voucher problem

The one-pass search in 14 languages, with its proof Pro: opens with a Pro, Premium or Ultimate pass

Counting pairs when prices repeat, and pairs with a gap Pro: opens with a Pro, Premium or Ultimate pass

Hash map, sorting or two pointers: choosing with measured numbers Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

In the one-pass pair search, why must each item look up its partner before the item itself goes into the map?

An array holds 10⁶ integers, most of them repeated. Count the index pairs i < j whose values add up to a target T. What do you store while scanning, what is the largest possible answer, and which integer type must hold it in Java or C++?

Readings arrive as an endless stream of integers between 0 and 10⁶. After each reading you must say whether any two readings so far add up to exactly T, using at most 1 MB of memory. What do you store, and what does each answer cost?

A colleague's function counts the index pairs whose values differ by exactly k. It returns twice the right answer when k is 0 and is correct otherwise. What is the likely bug, how do you fix it, and which tests would have caught it?

Key takeaways

References

Related tools