Matched pledges

A matching grant releases the moment two separate pledges add up to its target. The grant office does not want the amounts — it wants to know which two slots.

The problem

A fundraiser records every pledge as it arrives, one per numbered slot from 0. Most entries are positive, but a withdrawn pledge is posted as a negative correction, so amounts can go either way.

A matching grant releases when two pledges in two different slots add up to exactly the target. Report the two slot numbers, smaller first; at most one such pair exists, and if there is none report an empty list. The output is slots, not amounts — two donors may pledge the same figure, and the office has to credit the right two.

Input. pledges — a list of integers, the amount in each slot, in arrival order. target — an integer, the grant target.

Output. A list of two slot numbers [i, j] with i < j, or [] when no pair sums to target.

Example.

pledges = [250, 400, 150, 600, 100], target = 700   ->  [3, 4]

600 + 100 = 700. No other pair of slots reaches 700.

A second example, which shows why the positions matter:

pledges = [300, -50, 300, 20], target = 600   ->  [0, 2]

Two different donors pledged 300, and together they release the grant. Reporting the amounts would just say 300 and 300, which credits nobody.

Constraints.

• 2 <= len(pledges) <= 10^5
• -10^9 <= pledges[i] <= 10^9
• -10^9 <= target <= 10^9
• At most one pair of slots sums to target.

Hints

Approach

Brute force

Test every pair of slots: n(n - 1) / 2 additions, about 5 x 10^9 for 100,000 slots.

The tempting fix is to sort and walk two pointers inward, at O(n log n). It is faster, but it is the wrong shape — the answer is a pair of slots, and sorting is exactly the operation that throws slots away. Recovering them means sorting (amount, slot) pairs and re-ordering the result: more code, more memory, still slower than the map, and no use at all while pledges are still arriving.

The insight

Each pledge asks one membership question — has target - amount already been pledged? — and a hash map answers it in constant time, so a single pass replaces the pair loop.

The precondition is the order of the two operations: look up first, insert second. The map then holds only slots strictly earlier than the current one, so a hit is always a different pledge and i < j falls out without a check. Nothing has to be sorted or positive, which is why a negative correction costs nothing here.

Algorithm

1. Start an empty map from amount to the earliest slot holding it.
2. At slot j with amount a, compute target - a.
3. If that is a key, return [map[target - a], j].
4. Otherwise record a -> j, keeping the earlier slot if a is already a key.
5. Return [] when the record runs out.

Complexity

Time O(n) expected — one lookup and at most one insert per slot. Space O(n) in the worst case, when no two pledges repeat an amount.

Solution

"""Matched pledges — find the complement in a hash map, keeping the positions."""


def solve(pledges, target):
    seen = {}                       # pledge amount -> the earliest slot holding it
    for slot, amount in enumerate(pledges):
        need = target - amount
        # invariant: `seen` holds only slots strictly before `slot`, so a hit is
        # always a different pledge, never this one paired with itself.
        if need in seen:
            return [seen[need], slot]
        seen.setdefault(amount, slot)
    return []

TESTS = [
    (([250, 400, 150, 600, 100], 700), [3, 4]),
    (([300, -50, 300, 20], 600), [0, 2]),
    (([-40, 90, 50], 10), [0, 2]),
    (([7, 3], 10), [0, 1]),
    (([5, 5], 10), [0, 1]),
    (([5, 1], 10), []),
    (([120, 80, 45], 500), []),
]

Pitfalls

• Inserting before looking up. With pledges = [5, 1] and target = 10, slot 0 finds its own 5 in the map and reports [0, 0] — one pledge counted twice. Look up, then insert.
• Sorting first and returning the positions you land on. Those index the sorted copy, not the record; in the second example they name the two 300s as slots 2 and 3.
• Stopping early once amounts pass the target. That assumes every pledge is positive. [-40, 90, 50] with target = 10 matches slots 0 and 2, after an amount that already overshot.

Variants

• The badge scanned once — one pass and one map again, keyed on what has arrived rather than on what is missing.
• Settlement blocks — the same look-before-you-insert order, counting matches instead of returning the first.