Bracket through the archive

A retrofit needs one vertical bracket run straight down a wall of shelving. Every shelf it fails to slip past costs a drilled box, so fix it where the shelves already agree.

The problem

An archive room has a stack of shelves, each packed edge to edge with boxes of various widths. Every shelf is filled to the same total length, so boxes on one shelf line up with the next shelf's only by accident.

One vertical bracket must be fixed straight down through the whole stack. It passes a shelf harmlessly when it lands exactly on a gap between two boxes on that shelf; anywhere else it is drilled through a box. It cannot sit against either outer frame, so an offset of zero or of the full length is out.

Report the fewest boxes the bracket has to be drilled through.

Input. shelves — a list of lists of positive integers; shelves[i] is the box widths on shelf i, left to right. Every shelf has the same total.

Output. An integer, the fewest boxes any one offset drills.

Example.

shelves = [[3, 1, 2], [1, 3, 2], [2, 2, 2], [4, 2], [1, 2, 3], [5, 1]]   ->  2

Every shelf is 6 long. Offset 4 is a gap on the first four shelves, so the bracket only drills the last two. No offset clears five.

A second example, where a shelf with one box has no gap to offer:

shelves = [[4], [2, 2], [1, 3]]   ->  2

The single box on the top shelf spans the whole length, so it is drilled at any offset, and offsets 1 and 2 each clear one of the others but never both.

Constraints.

• 1 <= len(shelves) <= 10^4
• 1 <= len(shelves[i]), and the total number of boxes is at most 2 x 10^4
• 1 <= width <= 2^31 - 1
• Every shelf has the same total length.

Hints

Approach

Brute force

Try every offset from 1 to the shelf length minus 1, walking all the shelves at each one. Shelves can be billions of units long, so nearly all that work tests offsets no shelf could match.

The insight

The bracket only ever wants an offset where some shelf already has a gap, and the shelves it clears there is exactly how many shelves list that offset — so tally the offsets and take the biggest bucket.

All shelves share a total length, so an offset names the same physical place on every one and the buckets are comparable. Positive widths give the rest: each shelf's offsets strictly increase, so it drops at most one token into any bucket and the biggest bucket cannot double count. The boxes drilled are the shelves that did not vote for the winner.

Algorithm

1. Start an empty tally from offset to shelf count.
2. For each shelf, run a cumulative total over its widths, stopping before the last box — that final offset is the right frame, not a gap.
3. Increment the tally at each offset reached.
4. If the tally is empty, every shelf is one box: return the shelf count.
5. Otherwise return the shelf count minus the largest tally value.

Complexity

Time O(B) for B boxes in total, each added and looked up once. Space O(B): at most one key per gap.

Solution

"""Bracket through the archive — count shared gap offsets in a hash map."""


def solve(shelves):
    gaps = {}                       # offset from the left frame -> shelves with a gap there
    for boxes in shelves:
        offset = 0
        for width in boxes[:-1]:    # the last box ends at the right frame, not a gap
            offset += width
            # invariant: gaps[offset] counts shelves the bracket would clear
            # if it were fixed at this offset.
            gaps[offset] = gaps.get(offset, 0) + 1
    best = max(gaps.values()) if gaps else 0
    return len(shelves) - best

TESTS = [
    (([[3, 1, 2], [1, 3, 2], [2, 2, 2], [4, 2], [1, 2, 3], [5, 1]],), 2),
    (([[4], [2, 2], [1, 3]],), 2),
    (([[5], [5]],), 2),
    (([[1, 1, 1]],), 0),
    (([[1, 2, 2, 1], [3, 3]],), 0),
    (([[2, 1, 1, 2], [1, 1, 1, 1, 1, 1], [3, 3]],), 0),
    (([[6], [3, 3], [3, 3], [6]],), 2),
]

Pitfalls

• Including the last box's cumulative offset. Every shelf has that offset — it is the right frame — so the biggest bucket is always the shelf count and the answer is always 0.
• Returning the biggest bucket itself. That is the shelves cleared, not drilled. And [[5], [5]] has no gap at all, so max() over an empty tally raises instead of returning 2.
• Tallying widths rather than running offsets. [2, 2, 2] and [1, 2, 3] share the width 2, but their gaps are in different places.

Variants

• Beam through the swarm — the same biggest-bucket ending, with a two-dimensional direction as the key.
• Settlement blocks — running totals as keys again, counting matching pairs instead of the largest group.