Separate Black and White Balls — Medium Problem & Solution

Balls stand in a row: '0' is white and '1' is black. One step swaps two adjacent balls.

Difficulty: Medium
Topics: Strings, Greedy, Two Pointers
Asked at: Amazon, Google, Razorpay
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Balls stand in a row: '0' is white and '1' is black. One step swaps two adjacent balls.

Return the minimum number of steps needed to group all the white balls to the left and all the black balls to the right.

Example 1

Input: s = "101"
Output: 1
Explanation: Swap the first two to get "011".

Example 2

Input: s = "100"
Output: 2
Explanation: The single black ball has to travel past both whites.

Example 3

Input: s = "0111"
Output: 0
Explanation: Already separated.

Constraints

1 <= s.length <= 60000
s[i] is '0' or '1'

How to solve Separate Black and White Balls

Adjacent swaps can only exchange one white with one black, and each such exchange fixes exactly one out-of-order pair. So the answer is the number of (black, white) pairs that appear in the wrong order.

Approach

Sweep left to right keeping ones, the number of '1's seen so far.
On each '0', add ones to the total.
Return the total.

Why it works

The final arrangement is forced — all whites then all blacks — and relative order within a colour never matters since the balls of a colour are interchangeable. Each adjacent swap of a black with a white removes exactly one inversion, and no swap removes more, so the inversion count is both a lower bound and achievable.

Complexity

Time — O(n)
Space — O(1)

Pitfalls

Counting whites to the right of each black gives the same number but is easier to get off by one.
The total reaches about n²/4 ≈ 9 · 10^8 at the stated size — close to the int ceiling.
Simulating the swaps is O(n²) and unnecessary.

Reference solution

Python

def minimumSteps(s: str) -> int:
    ones = swaps = 0
    for ch in s:
        if ch == "1":
            ones += 1
        else:
            swaps += ones
    return swaps

JavaScript

var minimumSteps = function(s) {
    var ones = 0, swaps = 0;
    for (var i = 0; i < s.length; i++) {
        if (s.charAt(i) === "1") ones++; else swaps += ones;
    }
    return swaps;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue