#2938

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Separate Black and White Balls

Solve the "Separate Black and White Balls" problem by swapping adjacent balls to group all black balls to the right with the fewest steps.

two pointers string greedy

Problem Statement

You are given a binary string s of length n, where each character represents a ball on a table: '1' for black and '0' for white. The task is to group all black balls (1s) to the right side with the fewest adjacent swaps.

In each step, you can choose two adjacent balls and swap them. The goal is to determine the minimum number of swaps required to gather all black balls to the right side of the string.

Examples

Example 1

Input: s = "101"

Output: 1

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

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

All the black balls are already grouped to the right.

Constraints

1 <= n == s.length <= 105
s[i] is either '0' or '1'.

Solution Approach

Two-Pointer Scanning

Use two pointers to scan the string: one pointer starts at the leftmost position, and the other tracks the position of the last encountered white ball. Each time a black ball (1) is encountered, it is swapped with the white ball at the tracked position.

Tracking the Number of Swaps

Count the number of swaps by calculating how far each black ball is from its correct position, then sum these distances. This gives the total number of swaps needed to group all black balls to the right.

Greedy Approach for Minimizing Swaps

A greedy approach ensures that you minimize the number of swaps by moving each black ball only when necessary, and by swapping each black ball to the furthest right possible position.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity is O(n), where n is the length of the string, because we iterate over the string once. The space complexity is O(1), as we only use a few extra variables for the two pointers and swap counting.

What Interviewers Usually Probe

Can the candidate demonstrate efficient two-pointer usage for optimizing adjacent swap operations?
How well does the candidate recognize and utilize the greedy nature of the problem?
Does the candidate consider edge cases, such as when all black balls are already grouped?

Common Pitfalls or Variants

Common pitfalls

Failing to track the correct number of swaps or not considering the distance each black ball needs to move.
Overcomplicating the solution by using nested loops or unnecessary operations.
Not understanding the two-pointer method and relying on less efficient approaches.

Follow-up variants

What if the string was larger, close to the upper limit of 100,000? How would the solution scale?
What if the balls were not just two colors but had more varieties? How would the solution need to adapt?
What if the problem asked to group black balls to the left instead of the right?

FAQ

What is the optimal solution for the Separate Black and White Balls problem?

The optimal solution uses a two-pointer approach to minimize the number of adjacent swaps needed to group all black balls to the right of the string.

Why is the two-pointer approach used for this problem?

The two-pointer approach efficiently tracks and swaps balls while maintaining a minimal swap count, ensuring a time complexity of O(n).

What is the time complexity of the Separate Black and White Balls problem?

The time complexity is O(n), where n is the length of the string, as the algorithm performs a single scan of the string.

How does GhostInterview help with the Separate Black and White Balls problem?

GhostInterview assists in mastering the two-pointer technique, helping identify pitfalls and practice optimizing the solution with minimal swaps.

What is the key observation for solving the Separate Black and White Balls problem?

The key observation is that every 1 in the string should be swapped with every 0 on its right side, which can be efficiently tracked using two pointers.

terminal

Solution

Solution 1: Counting Simulation

We consider moving all the '1's to the rightmost side. We use a variable $cnt$ to record the current number of '1's that have been moved to the rightmost side, and a variable $ans$ to record the number of moves.

1

2

3

4

5

6

7

8

9

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

Continue Practicing

#2697 lexicographically smallest palindrome #3302 find the lexicographically smallest valid sequence #2486 append characters to string to make subsequence