Minimum Swaps to Group All 1's Together
Real-world version: Gathering The Boxes Into One BlockThe statement here is our own: the same inputs, outputs and technique.
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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def min_swaps(slots: list[int]) -> int:public int minSwaps(int[] slots)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 11 test cases: 11 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's