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.
In this approach, we will calculate the number of swaps needed to move all black balls to the right in a greedy manner. We iterate through the string and count the mismatches where a black ball (1) is found at a position where it should be a white ball (0). The goal is to minimize these mismatches by swapping the black balls with whites whenever necessary.
The function iterates over the string and counts the number of white balls ('0') it encounters. Each time a black ball ('1') is encountered, it adds the current count of white balls to the swap count, reflecting the swaps needed to move this black ball past all the white balls encountered so far.
Time Complexity: O(n) since we traverse the string once.
Space Complexity: O(1) since we are using only a constant amount of extra space.
This method utilizes a prefix sum array to keep track of the cumulative number of zeros up to each position in the string. A two-pointer approach then helps determine the best partition where all black balls should be on the right and all white balls should be on the left. This can help optimize the number of swaps by dynamically computing the transitions required at each potential partition.
This implementation calculates the prefix sum of zeros to optimize the determination of segments with fewer 1s that need to be swapped to reorder the sequence.
Time Complexity: O(n), since calculating the prefix sums and iterating through segment starts is linear.
Space Complexity: O(n) due to the storage of the prefix sum array.
We consider moving all the '1's to the rightmost side. We use a variable cnt to record the current number of '1's that have been moved to the rightmost side, and a variable ans to record the number of moves.
We traverse the string from right to left. If the current position is '1', then we increment cnt by one, and add n - i - cnt to ans, where n is the length of the string. Finally, we return ans.
The time complexity is O(n), where n is the length of the string. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n) since we traverse the string once. |
| Prefix Sum and Two-Pointer Optimization | Time Complexity: O(n), since calculating the prefix sums and iterating through segment starts is linear. |
| Counting Simulation | — |
| 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. |
Separate Black and White Balls - Leetcode 2938 - Python • NeetCodeIO • 11,365 views views
Watch 9 more video solutions →Practice Separate Black and White Balls with our built-in code editor and test cases.
Practice on FleetCode