The bracket under the shelf

A bookshop's window shelf rests on a single bracket. Put it under the wrong book and the shelf tips.

The problem

The shelf holds books in a fixed left-to-right order the display will not let you change. weights[i] is the weight of the i-th book in grams; an empty display stand counts as a book of weight 0.

The bracket sits directly under exactly one book. The shelf balances when the books strictly to the left of that book weigh the same as those strictly to its right; the book above the bracket rests on it and belongs to neither side.

Return the index of the leftmost balancing book, or -1 if no position balances the shelf. A bracket under the first book has nothing to its left, and nothing weighs 0 grams — the same holds right of the last book.

Input. weights — a list of non-negative integers in shelf order, at least one book long.

Output. The smallest index i where the books before i and the books after i weigh the same, or -1.

Example.

weights = [5, 4, 6, 2, 7, 8]  ->  3

Left of index 3: 5 + 4 + 6 = 15 grams. Right of it: 7 + 8 = 15 grams. The 2 g book at index 3 rests on the bracket, counting for neither side.

A second example, where nothing balances, and a third where an end position wins:

weights = [3, 8, 1, 4, 6, 2]  ->  -1
weights = [0, 0, 12]          ->  2

On the last shelf the bracket goes under the final book: the two empty stands left of it weigh 0 grams, and nothing at all sits to its right.

Constraints.

• 1 <= len(weights) <= 10^5
• 0 <= weights[i] <= 10^4

Hints

Approach

Brute force

For each candidate position, add the books to its left and those to its right: n positions costing up to n additions each, about 10¹⁰ additions on a shelf of 10⁵ books.

The insight

The right-hand weight is never a second sum to compute: it is the shelf total minus the running left weight minus the book on the bracket.

Every book sits in exactly one of three places relative to the bracket — left of it, on it, or right of it — so left + weights[i] + right equals the shelf total for every i. Substituting removes the right-hand scan, leaving the test left == total - left - weights[i], and both quantities are already in hand: the total is measured once, and the left weight rides along the sweep.

Algorithm

1. Compute total, the sum of every weight.
2. Set left = 0.
3. Walk i from 0 upward. If left == total - left - weights[i], return i.
4. Otherwise add weights[i] to left and carry on.
5. Return -1 if the sweep runs off the end.

Complexity

Time O(n) — one pass for the total, one for the sweep. Space O(1): two running integers and no prefix array, since each prefix is used once.

Solution

"""The bracket under the shelf — a running prefix weighed against the rest."""


def solve(weights):
    total = sum(weights)
    left = 0
    for i, weight in enumerate(weights):
        # invariant: left is the weight strictly before i, so the weight
        # strictly after i is total - left - weight, with no second scan
        if left == total - left - weight:
            return i
        left += weight
    return -1

TESTS = [
    (([5, 4, 6, 2, 7, 8],), 3),
    (([3, 8, 1, 4, 6, 2],), -1),
    (([0, 0, 12],), 2),
    (([9],), 0),
    (([0, 0],), 0),
    (([1, 0, 1, 0, 1],), 2),
]

Pitfalls

• Letting the book on the bracket count for the right side. The test left == total - left puts book i into the right-hand weight. On [5, 4, 6, 2, 7, 8] no prefix ever reaches half of 32, so it answers -1 instead of 3.
• Adding the book into left before the test. Index i is then judged with its own weight already on the left, shifting every answer: [0, 0, 12] comes back as -1 instead of 2.
• Returning any balancing index rather than the leftmost. A shelf of two empty stands, [0, 0], balances at both positions: collecting the matches and taking the last answers 1 where 0 is wanted.

Variants

• Reservoir ledger — the same prefix total, but stored, so arbitrary windows can be asked about later.
• Bypassing a gear stage — prefix and suffix are needed together at every index, so both are built rather than one derived from a total.