LeetCode 2938 - Separate Black and White Balls

The problem asks us to determine the minimum number of adjacent swaps required to rearrange a string of black and white balls such that all white balls (0s) are grouped on the left and all black balls (1s) are grouped on the right.

leetcodemediumtwo-pointersstringgreedy

LeetCode Problem 2938

Difficulty: 🟡 Medium
Topics: Two Pointers, String, Greedy

Solution

Problem Understanding

The problem asks us to determine the minimum number of adjacent swaps required to rearrange a string of black and white balls such that all white balls (0s) are grouped on the left and all black balls (1s) are grouped on the right. The input is a binary string s of length n, where each character represents a ball color. The output is an integer representing the minimum number of steps required to achieve the desired grouping.

The constraints 1 <= n <= 10^5 indicate that a naive solution that repeatedly swaps adjacent elements would be too slow. The problem guarantees that the string is non-empty and contains only characters '0' and '1'. Key edge cases include strings that are already grouped, strings with all balls of the same color, or strings that alternate between colors.

A crucial observation is that only the positions of the 1s relative to the 0s on their left matter because each 1 must "jump over" all preceding 0s to reach its final grouped position. The number of swaps needed for each 1 is equal to the number of 0s before it.

Approaches

The brute-force approach would simulate swapping adjacent balls iteratively until all black balls are on the right and all white balls on the left. While this approach is correct, it is highly inefficient. For each swap, we would need to scan the string for misplaced 1s or 0s, leading to a worst-case time complexity of O(n^2), which is unacceptable for n up to 10^5.

The optimal approach leverages the observation that the number of swaps for each 1 is equal to the number of 0s before it. By scanning the string once from left to right and maintaining a counter of encountered 0s, we can sum the required moves for each 1 efficiently in a single pass. This leads to an O(n) solution in both time and space, which is suitable for large inputs.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Simulate swaps iteratively
Optimal O(n) O(1) Count 0s and sum swaps for each 1

Algorithm Walkthrough

  1. Initialize a variable zero_count to 0. This variable keeps track of the number of white balls (0s) seen so far in the string.
  2. Initialize a variable steps to 0. This variable will accumulate the total number of swaps required.
  3. Iterate through each character c in the string s.
  4. If c is '0', increment zero_count by 1. This is because each 0 we encounter could potentially be jumped over by a subsequent 1.
  5. If c is '1', increment steps by zero_count. Each 1 must move past all the 0s seen so far to reach its final grouped position.
  6. After completing the iteration, steps contains the minimum number of adjacent swaps required.
  7. Return steps.

Why it works: Each 1 moves over all 0s to its left exactly once. By counting the number of 0s before each 1 and summing these counts, we obtain the minimal number of swaps necessary. This approach guarantees the minimality because moving any 1 over a 0 cannot be avoided, and we never double-count any swaps.

Python Solution

class Solution:
    def minimumSteps(self, s: str) -> int:
        zero_count = 0
        steps = 0
        for c in s:
            if c == '0':
                zero_count += 1
            else:  # c == '1'
                steps += zero_count
        return steps

Explanation: We maintain two counters: zero_count for white balls and steps for swaps. Every time we encounter a 0, we increment zero_count. For every 1, we add the current zero_count to steps, since each 1 must pass all the preceding 0s. The solution iterates once over the string and uses constant extra space.

Go Solution

func minimumSteps(s string) int64 {
    var zeroCount int64 = 0
    var steps int64 = 0
    for i := 0; i < len(s); i++ {
        if s[i] == '0' {
            zeroCount++
        } else { // s[i] == '1'
            steps += zeroCount
        }
    }
    return steps
}

Go-specific Notes: We use int64 for counters to safely handle large strings (up to 10^5), avoiding integer overflow. The iteration logic mirrors the Python solution, and strings in Go can be indexed directly to access individual characters.

Worked Examples

Example 1: s = "101"

Index Char zero_count steps
0 '1' 0 0
1 '0' 1 0
2 '1' 1 1

Result: 1 swap

Example 2: s = "100"

Index Char zero_count steps
0 '1' 0 0
1 '0' 1 0
2 '0' 2 0

steps for the first '1' is incremented by 2 after the loop completes. Result: 2 swaps

Example 3: s = "0111"

All black balls are already on the right, steps = 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the string of length n
Space O(1) Only two integer counters used, constant space

The algorithm avoids nested loops or additional data structures, making it efficient even for the maximum input size.

Test Cases

# Provided examples
assert Solution().minimumSteps("101") == 1  # minimal swap
assert Solution().minimumSteps("100") == 2  # multiple swaps
assert Solution().minimumSteps("0111") == 0  # already grouped

# Edge cases
assert Solution().minimumSteps("0") == 0  # single white ball
assert Solution().minimumSteps("1") == 0  # single black ball
assert Solution().minimumSteps("11111") == 0  # all black
assert Solution().minimumSteps("00000") == 0  # all white
assert Solution().minimumSteps("010101") == 9  # alternating colors
assert Solution().minimumSteps("00110011") == 8  # mixed pattern
Test Why
"101" Minimal swaps required
"100" Multiple swaps needed to group
"0111" Already grouped, zero swaps
"0" / "1" Single element edge case
"11111" / "00000" All same color edge cases
"010101" Alternating pattern to test summing
"00110011" Mixed pattern to stress counting logic

Edge Cases

All balls already grouped: Strings like "000111" or "111000" require zero swaps. The algorithm handles this naturally since steps only accumulates when a 1 has 0s before it.

Single-element strings: A string of length 1 ("0" or "1") should return 0. Our solution iterates over one character and does not increment steps, producing the correct result.

Alternating colors: Patterns like "010101" require multiple swaps per 1 since each 1 must pass all preceding 0s. The algorithm correctly accumulates steps for each 1, demonstrating its correctness in more complex arrangements.