Problem

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.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5
6

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:

1
2
3

Input: s = "0111"
Output: 0
Explanation: All the black balls are already grouped to the right.

Solution

Method 1 - Two Pointer Technique

The key insight is to count how many black balls (1) we have encountered so far. Every time we encounter a white ball (0), it should be swapped with the black balls(1) we had encountered on its left. The total number of swaps required is the sum of these individual swaps, ensuring all black balls(1) are moved to the right and all white balls(0) to the left.

Here is the approach:

  1. We count how many black balls (1) we have encountered so far with ones
  2. Every time we encounter a white ball (0), it needs to be swapped with the black balls (1) that are on its left.
  3. The total number of swaps is the sum of the swaps for every black ball (1) we encounter.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class Solution {
    public long minimumSteps(String s) {
        // Count of black balls ('1') encountered so far
        int ones = 0;
        
        // Total number of swaps required
        long swaps = 0;
        
        // Traverse each character in the string
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '0') {
                // If it's a white ball ('0'),
                // Add the number of black balls ('1') seen so far to swaps
                swaps += ones;
            } else {
                // If it's a black ball ('1'), increment the count of black balls
                ones++;
            }
        }
        
        return swaps;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def minimumSteps(self, s: str) -> int:
        ones = 0
        swaps = 0
        
        for char in s:
            if char == '0':
                swaps += ones
            else:
                ones += 1
        
        return swaps

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)