0611MediumTwo PointersStringGreedy

Sorting the Drum Rack

Tracked in this browser only

Trains the technique from

LeetCode 2938Separate Black and White Balls

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 loading rack holds n drums in a row, given as the string s. The character '0' is a light drum and '1' is a heavy drum.

In one move you pick two drums that sit next to each other and exchange their positions.

The rack is safe once every light drum sits somewhere to the left of every heavy drum. Return the smallest number of moves that makes the rack safe.

Examples

Example 1

Input: s = "1100"
Output: 4

One route is `1100` -> `1010` -> `1001` -> `0101` -> `0011`, which is four moves and leaves both light drums left of both heavy drums.

Example 2

Input: s = "111000"
Output: 9

Each of the three light drums has to travel past each of the three heavy drums, and nine moves reach `000111`.

Example 3

Input: s = "0000"
Output: 0

There is no heavy drum at all, so the rack is already safe.

Constraints

1 <= n == s.length <= 10^5
s[i] is either '0' or '1'.
The answer never exceeds 2.5 * 10^9.

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 minimum_steps(s: str) -> int:

Java

public long minimumSteps(String s)

The intended approach

Time O(n) — one pass over the string.Space O(1) — two integer counters.

Read the rack once from left to right, carrying the number of heavy drums met so far. Each time a light drum appears, add that carried count to the running total, because every heavy drum currently to its left has to end up on its right and one move exchanges it with exactly one neighbour. The running total after the single pass is the answer, and nothing but two integers is stored.

Pythonentry point: minimum_steps

def minimum_steps(s):
    # O(n) time, O(1) extra space. Walk the rack once from the left. Every
    # light drum has to pass every heavy drum currently sitting to its left,
    # and a single move moves it past exactly one of them, so the running
    # count of heavy drums seen so far is what this light drum contributes.
    heavy_so_far = 0
    moves = 0
    for ch in s:
        if ch == '1':
            heavy_so_far += 1
        else:
            moves += heavy_so_far
    return moves

The obvious version

Simulate moves directly on a mutable copy of the rack. Sweep left to right; whenever a heavy drum is immediately followed by a light drum, exchange the two and add one to the move count. Repeat sweeps until a full sweep exchanges nothing, then report the number of exchanges made.

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_minimum_steps(s):
    rack = list(s)
    moves = 0
    changed = True
    while changed:
        changed = False
        i = 0
        while i + 1 < len(rack):
            if rack[i] == '1' and rack[i + 1] == '0':
                rack[i], rack[i + 1] = rack[i + 1], rack[i]
                moves += 1
                changed = True
                i += 2
            else:
                i += 1
    return moves

How this problem was checked

Reference solution executed against 14 test cases — 14 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