Separate Black and White Balls

Med

#2618Time: O(N^2), where N is the length of the string `s`. The nested loops cause the algorithm to check approximately N^2/2 pairs in the worst case (e.g., a string of '1's followed by '0's).Space: O(1), as we only use a constant amount of extra space for loop variables and the counter. If we convert the string to a char array, it would be O(N), but this is not essential for the logic.

Patterns

Two Pointers Greedy

Data structures

String

Prompt

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 <= 10⁵
s[i] is either '0' or '1'.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly counts the number of 'inversions' in the string. An inversion is defined as a pair of a black ball ('1') appearing to the left of a white ball ('0'). The minimum number of adjacent swaps required to sort the balls is equal to the total number of such inversions. We can find this by using nested loops to check every possible pair of characters in the string.

Algorithm

Initialize a variable swaps to 0.
Use a nested loop structure. The outer loop iterates from the beginning of the string to the end, with index i.
If the character at s[i] is '1', start an inner loop with index j from i + 1 to the end of the string.
Inside the inner loop, if the character s[j] is '0', it means we have found an inversion pair ('1' before '0'). Increment the swaps counter.
After both loops complete, swaps will hold the total number of such pairs, which is the minimum number of adjacent swaps required.
Return the final swaps count.

Walkthrough

The fundamental insight is that to move all '1's to the right of all '0's, every '1' that is currently to the left of a '0' must be swapped past it. Each such pair (s[i] = '1', s[j] = '0') where i < j contributes to the total number of swaps. A brute-force method is to simply iterate through all possible pairs of indices (i, j) with i < j and count how many of them form an inversion.

1class Solution {2    public long minimumSteps(String s) {3        long swaps = 0;4        int n = s.length();5        // Convert string to char array for potentially faster access, though not strictly necessary.6        char[] balls = s.toCharArray();7 8        for (int i = 0; i < n; i++) {9            // If we find a black ball ('1')...10            if (balls[i] == '1') {11                // ...we count how many white balls ('0') are to its right.12                for (int j = i + 1; j < n; j++) {13                    if (balls[j] == '0') {14                        // Each '0' to the right of a '1' represents an inversion.15                        swaps++;16                    }17                }18            }19        }20        return swaps;21    }22}

Complexity

Time

O(N^2), where N is the length of the string `s`. The nested loops cause the algorithm to check approximately N^2/2 pairs in the worst case (e.g., a string of '1's followed by '0's).

Space

O(1), as we only use a constant amount of extra space for loop variables and the counter. If we convert the string to a char array, it would be O(N), but this is not essential for the logic.

Trade-offs

Pros

It's a straightforward implementation of the problem's definition in terms of inversions.
Easy to understand and reason about.

Cons

The quadratic time complexity makes it too slow for the given constraints, leading to a 'Time Limit Exceeded' error on large test cases.

This optimal approach avoids the nested loops by performing a single pass over the string. The key idea is to count inversions more efficiently. As we iterate from left to right, we keep track of the number of black balls ('1's) seen so far. When we encounter a white ball ('0'), we know it needs to be moved to the left of all the black balls we've already passed. The number of swaps required for this specific white ball is exactly the number of black balls currently to its left.

Algorithm

Initialize a variable swaps to 0 (as a long to prevent overflow).
Initialize a counter onesCount to 0.
Iterate through the string from left to right.
If the current character is a '1', increment onesCount.
If the current character is a '0', it means this '0' is positioned to the right of onesCount '1's. Each of these '1's must eventually be moved to the right of this '0'. This contributes onesCount swaps to the total. So, add the current onesCount to swaps.
After the loop finishes, swaps holds the total minimum number of steps. Return swaps.

Walkthrough

Instead of re-calculating for each '1', we can accumulate the result in one pass. Let's process the string from left to right. We maintain a count of the '1's we have seen so far. When we encounter a '0', we know that this '0' is in the wrong place relative to all the '1's we've already counted. To move this '0' to its correct sorted position (to the left of all '1's), it must be swapped past every one of the '1's we've seen. Therefore, we add the current count of '1's to our total swaps.

For example, in s = "1010":

i=0, s[0]='1': We've seen one '1'. onesCount = 1.
i=1, s[1]='0': We see a '0'. It must be swapped past the one '1' we've seen. swaps += 1. Total swaps = 1.
i=2, s[2]='1': We've now seen two '1's in total. onesCount = 2.
i=3, s[3]='0': We see another '0'. It must be swapped past the two '1's we've seen. swaps += 2. Total swaps = 1 + 2 = 3.

The final answer is 3.

1class Solution {2    public long minimumSteps(String s) {3        long swaps = 0;4        int onesCount = 0;5        6        for (char c : s.toCharArray()) {7            if (c == '1') {8                // Found a black ball, just increment the count.9                onesCount++;10            } else { // c == '0'11                // Found a white ball. It needs to be moved past all the black balls12                // we have encountered so far. The number of swaps needed for this13                // white ball is equal to the current count of black balls.14                swaps += onesCount;15            }16        }17        18        return swaps;19    }20}

Complexity

Time

O(N), where N is the length of the string `s`. We only iterate through the string once.

Space

O(1), as we only use a few variables to store the counts, regardless of the input size.

Trade-offs

Pros

Extremely efficient with a linear time complexity.
Uses constant extra space.
Simple to implement with a single loop.

Cons

The logic, while simple, might be slightly less intuitive than the direct brute-force counting of inversion pairs.

Solutions

Solution

1class Solution {2public3  long minimumSteps(String s) {4    long ans = 0;5    int cnt = 0;6    int n = s.length();7    for (int i = n - 1; i >= 0; --i) {8      if (s.charAt(i) == '1') {9        ++cnt;10        ans += n - i - cnt;11      }12    }13    return ans;14  }15}

1class Solution {2public:3  long long minimumSteps(string s) {4    long long ans = 0;5    int cnt = 0;6    int n = s.size();7    for (int i = n - 1; i >= 0; --i) {8      if (s[i] == '1') {9        ++cnt;10        ans += n - i - cnt;11      }12    }13    return ans;14  }15};

1class Solution:2    def minimumSteps(self, s: str) -> int: n = len(s) ans = cnt = 0 for i in range(n - 1, - 1, - 1): if s[i] == '1': cnt += 1 ans += n - i - cnt return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem