Scale Engineer

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 PointersGreedy
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 <= 105
  • 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.

class Solution {    public long minimumSteps(String s) {        long swaps = 0;        int n = s.length();        // Convert string to char array for potentially faster access, though not strictly necessary.        char[] balls = s.toCharArray();         for (int i = 0; i < n; i++) {            // If we find a black ball ('1')...            if (balls[i] == '1') {                // ...we count how many white balls ('0') are to its right.                for (int j = i + 1; j < n; j++) {                    if (balls[j] == '0') {                        // Each '0' to the right of a '1' represents an inversion.                        swaps++;                    }                }            }        }        return swaps;    }}

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.

Solutions

class Solution {public  long minimumSteps(String s) {    long ans = 0;    int cnt = 0;    int n = s.length();    for (int i = n - 1; i >= 0; --i) {      if (s.charAt(i) == '1') {        ++cnt;        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 →

Next problem