Watch 10 video solutions for Separate Black and White Balls, a medium level problem involving Two Pointers, String, Greedy. This walkthrough by NeetCodeIO has 11,365 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There are n balls on a table, each ball has a color black or white.
You are given a 0-indexed binary string s of length n, where 1 and 0 represent black and white balls, respectively.
In each step, you can choose two adjacent balls and swap them.
Return the minimum number of steps to group all the black balls to the right and all the white balls to the left.
Example 1:
Input: s = "101" Output: 1 Explanation: We can group all the black balls to the right in the following way: - Swap s[0] and s[1], s = "011". Initially, 1s are not grouped together, requiring at least 1 step to group them to the right.
Example 2:
Input: s = "100" Output: 2 Explanation: We can group all the black balls to the right in the following way: - Swap s[0] and s[1], s = "010". - Swap s[1] and s[2], s = "001". It can be proven that the minimum number of steps needed is 2.
Example 3:
Input: s = "0111" Output: 0 Explanation: All the black balls are already grouped to the right.
Constraints:
1 <= n == s.length <= 105s[i] is either '0' or '1'.Problem Overview: You are given a binary string where 0 represents a white ball and 1 represents a black ball. The task is to compute the minimum number of adjacent swaps needed so that all white balls appear on the left and all black balls appear on the right.
Approach 1: Greedy Counting (O(n) time, O(1) space)
The optimal observation is that every time a white ball (0) appears after one or more black balls (1), those balls must cross each other through adjacent swaps. While scanning the string from left to right, keep a counter of how many black balls you have seen so far. When you encounter a white ball, it needs to swap past all previously seen black balls, so you add that count to the answer. This effectively counts the number of inversions where 1 appears before 0. The algorithm performs a single linear pass over the string and uses a simple greedy accumulation strategy.
This approach works because each misplaced pair must be swapped exactly once in an optimal arrangement. There is no benefit in delaying swaps or performing extra movements. The greedy counting directly models the minimum number of required adjacent swaps.
Approach 2: Prefix Sum and Two-Pointer Optimization (O(n) time, O(n) space)
Another way to reason about the problem is by precomputing how many black balls exist before each index. Build a prefix array where prefix[i] stores the count of 1s from the start up to index i. Then iterate through the string and whenever you encounter a white ball (0), add prefix[i] to the total swaps because those black balls must move to the right of it. This approach uses the same inversion idea but expresses it through prefix sums.
You can also view the process through a two pointers perspective: one pointer tracks where the next white ball should land while the scan pointer moves across the string. Each displacement contributes to the swap count. Although the prefix array is not strictly necessary, it can make the reasoning clearer when explaining the algorithm in interviews.
Recommended for interviews: The greedy single-pass solution is what most interviewers expect. It demonstrates strong understanding of greedy reasoning and inversion counting while keeping both time complexity O(n) and space complexity O(1). Showing the prefix-sum interpretation can reinforce your reasoning, but the greedy counter is the cleanest and most efficient implementation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Counting | O(n) | O(1) | Best general solution. Single pass with constant memory. |
| Prefix Sum + Two-Pointer Reasoning | O(n) | O(n) | Useful for explaining inversion logic or when prefix counts are already available. |