# Separate Black and White Balls
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/separate-black-and-white-balls)
Canonical: https://scaleengineer.com/dsa/problems/separate-black-and-white-balls
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
---
## 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_.

**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
## Brute Force with Nested Loops
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## Optimal Single-Pass Approach
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public long minimumSteps(String s) {
        long swaps = 0;
        int onesCount = 0;
        
        for (char c : s.toCharArray()) {
            if (c == '1') {
                // Found a black ball, just increment the count.
                onesCount++;
            } else { // c == '0'
                // Found a white ball. It needs to be moved past all the black balls
                // we have encountered so far. The number of swaps needed for this
                // white ball is equal to the current count of black balls.
                swaps += onesCount;
            }
        }
        
        return swaps;
    }
}
```
### 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`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long minimumSteps(string s) {
    long long ans = 0;
    int cnt = 0;
    int n = s.size();
    for (int i = n - 1; i >= 0; --i) {
      if (s[i] == '1') {
        ++cnt;
        ans += n - i - cnt;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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

```