Separate Black and White Balls

Separate Black and White Balls

What is this problem about?

The Separate Black and White Balls interview question gives you a binary string where '0' represents a white ball and '1' represents a black ball. You can swap adjacent balls. The goal is to group all black balls to the right and all white balls to the left using the minimum number of adjacent swaps. This is a greedy string sorting problem similar to bubble sort analysis.

Why is this asked in interviews?

Microsoft, Amazon, Google, and Bloomberg ask this problem because it measures the ability to count inversions or derive an optimal swap count analytically rather than simulating all swaps. The greedy insight — each '0' needs to move left past all '1's to its left — yields an O(n) formula based on counting how many '1's precede each '0'. It tests whether candidates can see the mathematical structure behind a seemingly simulation-heavy problem.

Algorithmic pattern used

The pattern is greedy counting with two-pointer simulation. Track the number of '1's seen so far as you scan left to right. For each '0' encountered, it needs to be swapped past all the '1's before it — this requires exactly count_of_ones_so_far swaps for that '0'. Sum this across all '0's. Alternatively, use two pointers: a left pointer for '0' positions and a right pointer for '1' positions, computing distances.

Example explanation

String: "100110".

Scan left to right:

• Index 0: '1' → ones_count = 1.
• Index 1: '0' → needs 1 swap (past the one '1' at index 0). Total = 1.
• Index 2: '0' → needs 1 swap. Total = 2.
• Index 3: '1' → ones_count = 2.
• Index 4: '1' → ones_count = 3.
• Index 5: '0' → needs 3 swaps. Total = 5.

Minimum swaps: 5.

Final arrangement: "000111".

Common mistakes candidates make

• Simulating actual swaps in O(n^2) — this is correct but inefficient; the counting approach is O(n).
• Counting ones_count for '1's instead of incrementing it — increment when you see '1', add to total when you see '0'.
• Not recognizing that this is equivalent to counting inversions in the binary array (all (1,0) pairs where 1 precedes 0).
• Trying to use a sort — sorted() gives the final state but doesn't count swaps.

Interview preparation tip

For the Separate Black and White Balls coding problem, the two-pointer greedy string interview pattern is the efficient O(n) solution. The key insight is that the minimum number of swaps equals the number of inversions in the binary sequence — pairs where a '1' appears before a '0'. Microsoft and Bloomberg interviewers appreciate when you draw the parallel to bubble sort inversion counting. Practice this: "how many adjacent swaps to sort a binary array?" — it's a classic variation of the minimum swaps problem.