0645MediumArraySliding Window

Gathering The Boxes Into One Block

Tracked in this browser only

Trains the technique from

LeetCode 1151Minimum Swaps to Group All 1's Together

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A storage rail is a row of positions. slots[i] is 1 when position i holds a box and 0 when it is empty.

One swap exchanges the contents of any two positions on the rail; the two positions need not be neighbours. Return the fewest swaps that leave the boxes in one unbroken block, meaning no empty position sits between two boxes. A rail with no boxes, or with only one, already satisfies this.

Examples

Example 1

Input: slots = [1, 0, 1, 1, 0, 1, 1]
Output: 1

The rail holds 5 boxes. Swapping position 0 with position 4 leaves the boxes on positions 2 through 6 with nothing empty in between, so 1 swap is enough.

Example 2

Input: slots = [0, 0, 1, 1, 1]
Output: 0

The 3 boxes at positions 2, 3 and 4 already sit next to each other with no empty position between them, so no swap is needed.

Example 3

Input: slots = [1, 0, 1, 0, 1, 0, 1, 0, 1]
Output: 2

The rail holds 5 boxes. Swapping position 0 with position 5, then position 2 with position 7, leaves the boxes on positions 4 through 8 with nothing empty in between, so 2 swaps are enough.

Constraints

1 <= slots.length <= 10^5
slots[i] is either 0 or 1.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_swaps(slots: list[int]) -> int:

Java

public int minSwaps(int[] slots)

The intended approach

Time O(n) — one pass, with the window updated in constant time per position.Space O(1) — running counters only.

Count the boxes first. However the swaps are chosen, the boxes end up occupying one stretch of the rail whose length is that count, and turning a chosen stretch into the block costs one swap per empty position inside it, since each such position is filled by a box brought in from outside. So slide a window of that fixed length along the rail, keeping a running count of the boxes it covers by adding the position entering and subtracting the one leaving, and subtract the best count from the total. Rails with at most one box need nothing.

Pythonentry point: min_swaps

def min_swaps(slots):
    # O(n) time, O(1) space: whatever the swaps are, the boxes finish inside one
    # window whose length equals the number of boxes, and the swaps a chosen
    # window costs are exactly the empty positions in it. So run a window of that
    # fixed length along the shelf, keep the count of boxes inside it, and report
    # the total box count minus the largest count any window reached.
    total = 0
    for v in slots:
        total += v
    if total <= 1:
        return 0
    inside = 0
    best = 0
    for i in range(len(slots)):
        inside += slots[i]
        if i >= total:
            inside -= slots[i - total]
        if i >= total - 1 and inside > best:
            best = inside
    return total - best

The obvious version

Count the boxes, then for every position where a stretch of that length fits, count the empty positions inside that stretch from scratch and keep the smallest such count.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_swaps(slots):
    n = len(slots)
    total = 0
    for v in slots:
        total += v
    if total == 0:
        return 0
    best = None
    for start in range(0, n - total + 1):
        holes = 0
        for i in range(start, start + total):
            if slots[i] == 0:
                holes += 1
        if best is None or holes < best:
            best = holes
    return best

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in