Separate Black and White Balls

Medium
857.

Separate Black and White Balls

Separate Black and White Balls is a medium coding problem on strings, greedy and two pointers, asked in Amazon, Google and Razorpay interviews.

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'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var minimumSteps = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Separate Black and White Balls — Problem & Solution

Separate Black and White Balls solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Separate Black and White Balls is a medium coding problem on strings, greedy and two pointers, asked in Amazon, Google and Razorpay interviews.

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'

Hints for Separate Black and White Balls

  1. Hint 1

    Every white ball must end up left of every black ball, and adjacent swaps preserve the relative order within each colour.

  2. Hint 2

    So a white ball's cost is the number of black balls currently to its left.

  3. Hint 3

    Sweep once, keeping a running count of black balls seen.

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

  1. Sweep left to right keeping ones, the number of '1's seen so far.
  2. On each '0', add ones to the total.
  3. 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

Java

public static int minimumSteps(String s) {
    long ones = 0, swaps = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '1') ones++; else swaps += ones;
    }
    return (int) swaps;
}

C++

int minimumSteps(string s) {
    long long ones = 0, swaps = 0;
    for (char ch : s) {
        if (ch == '1') ones++; else swaps += ones;
    }
    return (int) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms