Separate Black and White Balls

LeetCode 2938: Separate Black and White Balls Solution & Explanation

Problem Overview

TL;DR: Use a two-pointer approach to calculate the total displacement required to move every '0' (white ball) to its correct sorted position at the start of the string.

The problem asks us to sort a binary string s such that all '0's (white balls) appear before all '1's (black balls). We are restricted to swapping adjacent characters. The goal is to return the minimum number of swaps required to achieve this grouped state. This is a classic variation of calculating the number of inversions or determining the cost to sort an array with specific constraints.

For LeetCode 2938, the input size can be up to $10^5$, requiring a linear time solution.

Brute Force Approach for Separate Black and White Balls

The naive approach attempts to simulate the sorting process directly. We could repeatedly scan the string, finding the first occurrence where a '1' is immediately followed by a '0' ("10"), and swap them. We repeat this process until no such pairs exist.

Pseudo-code

while string is not sorted:
    found_swap = false
    for i from 0 to n-2:
        if s[i] == '1' and s[i+1] == '0':
            swap(s[i], s[i+1])
            increment swap_count
            found_swap = true
return swap_count

Time Complexity Analysis

The time complexity of this simulation is $O(N^2)$. In the worst-case scenario (e.g., 111...000), every '0' must bubble past every '1'. With $N=10^5$, $N^2$ results in $10^{10}$ operations, which will inevitably cause a Time Limit Exceeded (TLE) error.

Algorithm Strategy: Two Pointer Patterns

1. Initialize Pointers:

   • insert_pos (Slow Pointer): Starts at 0. This tracks the index where the next '0' should be placed to maintain the sorted order.
   • current (Fast Pointer): Iterates from 0 to n-1.

2. Accumulator:

   • Maintain a variable total_swaps (must be a 64-bit integer) to store the result.

3. Iteration Logic:

   • Iterate through the string s using current.
   • If s[current] is '0':
     • Calculate the displacement: current - insert_pos.
     • Add this value to total_swaps.
     • Increment insert_pos to prepare for the next '0'.
   • If s[current] is '1', we simply continue (the insert_pos does not move, effectively increasing the potential displacement for future '0's).

4. Return:

   • Return total_swaps.

Execution Flow

Consider the input s = "11001".

1. Initialization:

   • total_swaps = 0
   • insert_pos = 0

2. Step 1 (current = 0):

   • s[0] is '1'.
   • Ignore. insert_pos remains 0.

3. Step 2 (current = 1):

   • s[1] is '1'.
   • Ignore. insert_pos remains 0.

4. Step 3 (current = 2):

   • s[2] is '0'.
   • Target position is insert_pos (0).
   • Cost: 2 - 0 = 2.
   • total_swaps becomes 2.
   • Increment insert_pos to 1.

5. Step 4 (current = 3):

   • s[3] is '0'.
   • Target position is insert_pos (1).
   • Cost: 3 - 1 = 2.
   • total_swaps becomes 2 + 2 = 4.
   • Increment insert_pos to 2.

6. Step 5 (current = 4):

   • s[4] is '1'.
   • Ignore.

7. Final Result: 4.

   • Explanation: The first '0' jumped over two '1's. The second '0' jumped over two '1's. Total 4 swaps.

Proof of Correctness

The algorithm relies on the invariant that insert_pos always points to the earliest index that is not yet finalized as a '0'. When we encounter a '0' at index current, every index between insert_pos and current must be occupied by '1's (otherwise, those positions would have been filled by previous '0's and insert_pos would have advanced).

Therefore, the distance current - insert_pos is exactly equal to the number of '1's preceding the current '0'. Since we must swap the '0' with every preceding '1' to group them correctly, the sum of these distances yields the minimum total swaps. This is mathematically equivalent to counting inversions where i < j but s[i] == '1' and s[j] == '0'.

Pattern Reuse Notes

The "Two Pointers - In-place Array Modification" pattern is fundamental for array manipulation problems. The logic used in LeetCode 2938 to track an insertion index (insert_pos) while iterating is identical to:

• LeetCode 26: Remove Duplicates from Sorted Array (Tracks unique element position)
• LeetCode 27: Remove Element (Tracks position for non-removed elements)
• LeetCode 75: Sort Colors (Tracks boundaries for 0s, 1s, and 2s)
• LeetCode 80: Remove Duplicates from Sorted Array II (Tracks valid placement for allowed duplicates)

In all these problems, one pointer iterates through the data, while a second pointer marks the boundary of the "processed/valid" data.

Reference Implementation

C++ Solution for LeetCode 2938

1class Solution {
2public:
3    long long minimumSteps(string s) {
4        long long total_swaps = 0;
5        int insert_pos = 0; // The slow pointer
6        
7        // Iterate with current as the fast pointer
8        for (int current = 0; current < s.length(); ++current) {
9            if (s[current] == '0') {
10                // The cost to move this '0' to the insert_pos
11                total_swaps += (current - insert_pos);
12                
13                // Advance the insert position for the next '0'
14                insert_pos++;
15            }
16        }
17        
18        return total_swaps;
19    }
20};

Java Solution for LeetCode 2938

1class Solution {
2    public long minimumSteps(String s) {
3        long totalSwaps = 0;
4        int insertPos = 0; // The slow pointer
5        
6        // Iterate with current as the fast pointer
7        for (int current = 0; current < s.length(); current++) {
8            if (s.charAt(current) == '0') {
9                // The cost to move this '0' to the insertPos
10                totalSwaps += (current - insertPos);
11                
12                // Advance the insert position for the next '0'
13                insertPos++;
14            }
15        }
16        
17        return totalSwaps;
18    }
19}

Python Solution for LeetCode 2938

1class Solution:
2    def minimumSteps(self, s: str) -> int:
3        total_swaps = 0
4        insert_pos = 0 # The slow pointer
5        
6        # Iterate with current as the fast pointer
7        for current, char in enumerate(s):
8            if char == '0':
9                # The cost to move this '0' to the insert_pos
10                total_swaps += (current - insert_pos)
11                
12                # Advance the insert position for the next '0'
13                insert_pos += 1
14                
15        return total_swaps