Separate Black and White Balls

Problem Description

You are given a binary string s representing n balls on a table, where 1 represents a black ball and 0 represents a white ball. The goal is to determine the minimum number of adjacent swaps needed to group all black balls to the right and all white balls to the left.

Key Insights

• Each 1 (black ball) should be moved to the right side of the string.
• Each 0 (white ball) should be moved to the left side.
• The number of swaps required corresponds to the number of 0s that are to the right of each 1.
• A two-pointer approach can efficiently track the positions of 0s and 1s to calculate the required swaps.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we will use a two-pointer technique:

1. Initialize a counter for the number of swaps needed and a pointer to count the number of 0s encountered.
2. Iterate through the string, and for each 1 encountered, add the count of 0s to the swaps counter.
3. Continue this process until the end of the string.
4. The total count in the swaps counter will represent the minimum number of adjacent swaps needed.

Code Solutions