Separate Black and White Balls

medium two pointers string greedy

Problem

You are given a binary string s where 1 is a black ball and 0 is a white ball. In one step you may swap two adjacent balls. Return the minimum number of steps to move all black balls (1) to the right and all white balls (0) to the left.

Key insight: a black ball at index i must cross every white ball that lies to its right. Equivalently, each white ball must be passed by every black ball sitting to its left, and adjacent swaps move a ball exactly one position — so the answer is the sum of those crossings.

Inputs = "101"

Output1

Swap s[0] and s[1] to get "011". The single 0 at index 1 has one 1 to its left, so it takes 1 step.

s (binary string of 0s and 1s)

def minimumSteps(s: str) -> int:
    ones = 0       # number of 1s (black balls) seen so far
    steps = 0      # running answer
    for ch in s:
        if ch == '1':
            ones += 1            # one more black ball on the left
        else:                    # ch == '0', a white ball
            steps += ones        # every left 1 must cross this 0
    return steps

function minimumSteps(s) {
  let ones = 0;          // number of 1s (black balls) seen so far
  let steps = 0;         // running answer (use BigInt for huge inputs)
  for (const ch of s) {
    if (ch === '1') {
      ones += 1;         // one more black ball on the left
    } else {             // ch === '0', a white ball
      steps += ones;     // every left 1 must cross this 0
    }
  }
  return steps;
}

long minimumSteps(String s) {
    long ones = 0;            // number of 1s (black balls) seen so far
    long steps = 0;           // running answer
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '1') {
            ones++;           // one more black ball on the left
        } else {              // '0', a white ball
            steps += ones;    // every left 1 must cross this 0
        }
    }
    return steps;
}

long long minimumSteps(string s) {
    long long ones = 0;       // number of 1s (black balls) seen so far
    long long steps = 0;      // running answer
    for (char ch : s) {
        if (ch == '1') {
            ones++;           // one more black ball on the left
        } else {              // '0', a white ball
            steps += ones;    // every left 1 must cross this 0
        }
    }
    return steps;
}

Explanation

We want every black ball (1) on the right and every white ball (0) on the left, using the fewest adjacent swaps. The trick is to never actually move anything — we just count the crossings that any valid sequence of swaps must perform.

Look at one white ball. In the final arrangement it ends up to the left of every black ball. So it must end up left of exactly the black balls that currently sit to its left. An adjacent swap moves a ball one slot, and the only way a black ball ends up to the right of this white ball is to swap past it once. Therefore this white ball contributes one step per black ball currently on its left.

Scanning left to right, we keep a counter ones of black balls seen so far. Each time we hit a 1 we increment ones. Each time we hit a 0 we add ones to the answer — that is exactly how many black balls this white ball has to let through.

This is a greedy / two-pointer accounting: ones acts like a pointer summarizing everything to the left, so a single pass suffices. No swap is ever simulated, yet the total is provably optimal because each crossing is unavoidable and each adjacent swap resolves exactly one crossing.

Example s = "100": the first 0 sees one 1 (+1), the second 0 also sees one 1 (+1), total 2 — matching the two swaps "100" → "010" → "001". Because the answer can reach about n²/4 ≈ 2.5×10⁹ for n = 10⁵, use a 64-bit integer (long).

Time: O(n) Space: O(1)