Separate Black and White Balls - Practice Coding Problems

Separate Black and White Balls - 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.

Input & Output

Example 1 — Basic Mixed Sequence

$ Input: s = "101"

› Output: 1

💡 Note: We can group all black balls to the right by swapping s[0] and s[1]: "101" → "011". This takes 1 step.

Example 2 — Multiple Swaps Needed

$ Input: s = "0110"

› Output: 2

💡 Note: We can group all black balls to the right in 2 steps: "0110" → "1010" → "1100". The white ball at index 0 needs 2 swaps to move past both black balls.

Example 3 — Already Sorted

$ Input: s = "0011"

› Output: 0

💡 Note: All white balls are already on the left and black balls on the right. No swaps needed.

Constraints

1 ≤ s.length ≤ 10⁵
s[i] is either '0' or '1'

Visualization

Tap to expand

Understanding the Visualization

Input

Mixed sequence of black (1) and white (0) balls

Process

Count minimum adjacent swaps needed

Output

Number of swaps to group whites left, blacks right

Key Takeaway

🎯 Key Insight: Each white ball must pass all black balls to its right - count blacks while scanning backwards

Asked in

M Meta 25 G Google 20 μ Microsoft 15

The key insight is that each white ball needs to move past all black balls to its right. The optimal greedy approach scans right to left, counting black balls and adding this count to the total for each white ball encountered. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n³)	O(n)	Simulate the actual swapping process by repeatedly finding and moving misplaced balls
Greedy Counting	O(n)	O(1)	Count black balls encountered while scanning, each white ball needs to move past all blacks to its right

Brute Force Simulation — Algorithm Steps

Step 1: Scan for any white ball that has black balls to its right
Step 2: Swap the white ball with its right neighbor if it's black
Step 3: Repeat until all balls are in correct positions

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Mixed black and white balls

Scan & Swap

Find white balls followed by black balls and swap them

Repeat

Continue until all balls are sorted

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(char* s) {
    int n = strlen(s);
    int steps = 0;
    
    bool changed = true;
    while (changed) {
        changed = false;
        for (int i = 0; i < n - 1; i++) {
            // If white ball (0) is followed by black ball (1), swap them
            if (s[i] == '0' && s[i + 1] == '1') {
                char temp = s[i];
                s[i] = s[i + 1];
                s[i + 1] = temp;
                steps++;
                changed = true;
            }
        }
    }
    
    return steps;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

In worst case, need O(n²) swaps and each scan takes O(n) time

⚠ Quadratic Growth

Space Complexity

O(n)

Need to store the string as mutable array for swapping

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler