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.
- 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 <= 60000s[i] is '0' or '1'
Hints for Separate Black and White Balls
Hint 1
Every white ball must end up left of every black ball, and adjacent swaps preserve the relative order within each colour.
Hint 2
So a white ball's cost is the number of black balls currently to its left.
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
- Sweep left to right keeping
ones, the number of'1's seen so far. - On each
'0', addonesto 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^8at the stated size — close to theintceiling. - 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 swapsJava
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