The Target Hunt

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

Domain
Python
Difficulty
medium
Seniority
L5
Asked in
Amazon

Problem

A reconciliation job pairs up transaction amounts that offset to a fixed target. Given a list nums of integers and an integer target, return every [x, y] pair summing to target, where each list element belongs to at most one pair. A value repeated at different positions can take part in that many separate pairs, so [1, 1, 2, 2] with target 3 yields two [1, 2] pairs rather than one. List the earlier-positioned value first inside each pair, and return the pairs in the order their second (completing) element appears while moving through the list left to right.

Pairs that hit a target. Every one of them.

Example 1

Input:

nums = [2,4,3,5,7,8,1], target = 9

Output:

[[4,5],[2,7],[8,1]]

Example 2

Input:

nums = [1,1,2,2], target = 3

Output:

[[1,2],[1,2]]

Worked solution and explanation

What this really is

Strip the costume and this is consume-on-match pairing over a multiset. The real skill is tracking how many copies of each value are still unpaired, not merely whether you have seen a value. A set-based two-sum lookup feels right and sails through every all-distinct case, then quietly breaks the moment a value repeats: it cannot tell that [1, 1, 2, 2] summing to 3 owes you two separate [1, 2] pairs. The trap is treating 'have I seen the complement' as a yes or no question. Forget to decrement a count after consuming an element and that element gets reused, so you emit phantom pairs. Get the bookkeeping wrong and your reconciliation double-counts.

The two simpler tools that both fail

A plain set of seen values
Records only presence, so it cannot represent that two 1s are each still available. On [1, 1, 2, 2] target 3 it either emits one [1, 2] (if you remove on match) or unbounded [1, 2]s, and on [5, 5, 5] target 10 it emits a phantom third 5 pairing. Multiplicity is wrong either way.
Brute force, pair by first element
Nested loops with a used flag get multiplicity right but emit in first-element order. On [2, 4, 3, 5, 7, 8, 1] target 9 it yields [[2,7],[4,5],[8,1]], not the required completion order [[4,5],[2,7],[8,1]]. Wrong order, fails the contract.

Only a per-value count, decremented as copies are consumed, gives correct multiplicity AND completion order in a single pass. That is why this shape needs more than a set.

Break down the requirements

Step 1: Track available copies, not just presence

Keep a dict mapping each value passed so far to how many unmatched copies are still available. That count, not a bare membership flag, is what lets duplicates pair more than once and lets a lookup stay O(1) without sorting, which would destroy the completion order.

Step 2: Move left to right and look up the complement

Sweep the list left to right. For the current value compute complement = target - current, and check whether an available copy of that complement still exists.

Step 3: Emit earlier-first and consume one copy

When the complement is available, record the pair as [complement, current] (the earlier-positioned value leads) and decrement the complement's count so it cannot be reused. Otherwise add the current value as newly available. This naturally yields multiple pairs for repeated values at distinct positions.

The solution

Single pass with a count of available complements
def find_pairs(nums: list[int], target: int) -> list[list[int]]:
    available = {}
    pairs = []
    for current in nums:
        complement = target - current
        if available.get(complement, 0) > 0:
            pairs.append([complement, current])
            available[complement] -= 1
        else:
            available[current] = available.get(current, 0) + 1
    return pairs

One left-to-right pass; each lookup and update is O(1).

Common follow-up questions