The Complement Hunt

An easy Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
easy
Seniority
L4

Problem

A fraud monitor ingests a stream of transaction amounts in arrival order, watching for two that were split to reach a flagged target. As each amount arrives, report the position of the earliest earlier amount that pairs with it to reach the target, or -1 if no earlier amount does.

Every number is looking for its other half.

Example 1

Input:

amounts = [2,7,11,15], target = 9

Output:

[-1,0,-1,-1]

Example 2

Input:

amounts = [3,4,3,6], target = 6

Output:

[-1,-1,0,-1]

Worked solution and explanation

What this really is

This is an online pairing search wearing a fraud-monitor costume. The amounts arrive in order, and every one of them, the instant it lands, has to answer a question about everything that came before it: is my complement (target - amount) already here, and if so, where did it first show up? Anyone can rescan the whole prefix on each arrival, but that is a quadratic pile of re-reading. The load-bearing move is keeping a live map from each amount to the earliest position it appeared, so every arrival becomes one O(1) lookup. And the record-then-check ordering is a trap: stamp the current amount into the map before you look, and it will happily pair with itself the moment target is twice its value.

Why a seen-set is not enough

A plain seen-set is the reflex simplification, and here it quietly fails. The answer is not 'did a partner exist' but WHICH position that partner occupies, so you must store the amount-to-index association a set cannot hold. And because a repeated amount must point back to its FIRST appearance, you record a position only when the amount is new. Those two requirements are exactly why the structure is a map keyed by value, not a membership set.

A seen-set
Tells you a complement was seen, but not its position, so it cannot build the required list of indices. It also has no way to honor the earliest-occurrence rule when a value repeats.
A value-to-index map
Stores each amount's first position, so every arrival returns the exact partner index in O(1), and repeated amounts keep pointing at the earliest match.

How to get there

Step 1: Look before you record

Compute the complement (target - current) and read it out of the map before touching the map. If it is present, that stored value is the earliest earlier partner's position; if not, the answer for this arrival is -1. Looking before recording is what keeps an amount from pairing with itself, since the current amount is not in the map yet.

Step 2: Record only first appearances

Write the current amount into the map only when it is not already a key. That single guard preserves the earliest-position rule: a later repeat of the same amount must still point back to where that value first appeared, so you never overwrite the stored index.

The solution

Single-pass complement lookup over the stream
def earliest_partners(amounts, target):
    first_index = {}          # amount -> earliest position it appeared
    partners = []
    for i, amount in enumerate(amounts):
        complement = target - amount
        partners.append(first_index.get(complement, -1))
        if amount not in first_index:
            first_index[amount] = i
    return partners

Common follow-up questions