Ribbon pairs

A haberdashery keeps its offcut ribbon on a numbered rack. An order needs a precise length, and it has to be met by joining exactly two spools.

The problem

The rack holds spools of ribbon, each measured in whole centimetres. Position 0 is the leftmost slot, and the lengths are in no particular order — offcuts are put back wherever there is room.

An order for needed centimetres arrives. Find two different slots whose ribbon lengths add up to needed exactly, and report their positions with the smaller position first. At most one such pair exists on the rack. If there is none, the order cannot be filled and the answer is empty.

Input. spools — a list of integers, the length of the ribbon in each slot, left to right. needed — an integer, the length the order calls for.

Output. A list [i, j] with i < j and spools[i] + spools[j] == needed, or [] if no pair works.

Example.

spools = [42, 15, 27, 8], needed = 50   ->  [0, 3]

42 and 8 make 50. The other pairs give 57, 69, 23, 35 and 50 is not among them.

A second example, where the two spools are the same length:

spools = [30, 30, 12], needed = 60      ->  [0, 1]

Two separate 30 cm offcuts fill the order. One 30 cm spool used twice does not — there is only one of it in slot 0.

Constraints.

• 2 <= len(spools) <= 10^5
• 1 <= spools[i] <= 10^6
• 2 <= needed <= 2 * 10^6
• At most one valid pair exists.

Hints

Approach

Brute force

Pair every slot with every slot to its right and test the sum. That is n * (n - 1) / 2 additions — five billion of them on a rack of 10^5 spools — and every pair is examined even though only one of them matters.

The insight

A spool of length L does not need a search; it needs the number needed - L, so the question becomes membership, not comparison.

Once the target is a single number, a dictionary from length to position answers it in constant time. Walking left to right and storing each spool after testing it keeps the dictionary holding exactly the slots strictly left of the current one. That is why a pair is never missed — the right-hand member of the true pair finds its partner already stored — and why a spool can never pair with itself.

Algorithm

1. Start an empty dictionary from length to position.
2. For each position j and length L, compute partner = needed - L.
3. If partner is a key, return [dictionary[partner], j].
4. Otherwise store L -> j and continue.
5. If the walk ends, return [].

Complexity

Time O(n) — one pass, one dictionary probe and at most one insert per slot. Space O(n) — in the worst case every length is stored before a pair is found.

Solution

"""Ribbon pairs — one pass, remembering every length already walked past."""


def solve(spools, needed):
    # seen maps a length to the position it was found at, for spools strictly
    # left of the current one. Looking up before storing is what stops a spool
    # from pairing with itself.
    seen = {}
    for position, length in enumerate(spools):
        partner = needed - length
        if partner in seen:
            return [seen[partner], position]
        seen[length] = position
    return []

TESTS = [
    (([42, 15, 27, 8], 50), [0, 3]),
    (([30, 30, 12], 60), [0, 1]),
    (([5, 75, 25, 20], 45), [2, 3]),
    (([7, 3], 10), [0, 1]),
    (([25, 60, 25], 50), [0, 2]),
    (([9, 4, 6], 100), []),
]

Pitfalls

• Storing the spool before testing it. With spools = [25, 60, 25] and needed = 50, slot 0 finds its own 25 in the dictionary and returns [0, 0], which is one spool cut in half rather than two.
• Sorting the rack first. Sorting makes a two-pointer sweep possible, but the positions you then report are positions in the sorted copy, not slots on the rack. Slot numbers are the answer, so either sort pairs of (length, position) or do not sort at all.
• Returning [j, i]. Discovery happens at the right-hand slot, so the stored position is the smaller one and belongs first.

Variants

• Shared sightings — the same rescan-to-lookup move when only membership matters, with no position to keep.