Separate Black and White Balls solution and explanation
Google
9 more videos on this problem
Separate Black and White Balls - Leetcode 2938 - PythonNeetCodeIO · 8:15 · 11K views
Separate Black and White Balls | 2 Simple Ways | Leetcode 2938 | codestorywithMIKcodestorywithMIK · 13:23 · 8K views
Separate Black and White Balls | Leetcode 2938Techdose · 11:50 · 1K views
Separate Black and White Balls - Leetcode 2938 - PythonCheatCode Ninja · 5:12 · 505 views
SEPARATE BLACK AND WHITE BALLS | LEETCODE 2938 | PYTHON SOLUTIONCracking FAANG · 3:22 · 488 views
2938. Separate Black and White Balls (Leetcode Medium)Programming Live with Larry · 5:24 · 358 views
Leetcode 2938. Separate Black and White BallsElite Code · 20:23 · 289 views
Separate Black and White Balls - LeetCode 2938 - PythonAlpha-Code · 14:36 · 112 views
Separate Black and White Balls - Leetcode 2938 - JavaCode With K5KC · 4:44 · 105 views
2938. Separate Black and White Balls - Leetcode - Python / C++Source Code · 7:47 · 55 views
The 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.
Example 1:
Input: s = "101" Output: 1 Explanation: 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 Explanation: 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 Explanation: All the black balls are already grouped to the right.
Constraints:
1 <= n == s.length <= 105s[i]is either'0'or'1'.
Approach overview
Problem Overview: You are given a binary string where 0 represents a white ball and 1 represents a black ball. The task is to compute the minimum number of adjacent swaps needed so that all white balls appear on the left and all black balls appear on the right.
Approach 1: Greedy Counting (O(n) time, O(1) space)
The optimal observation is that every time a white ball (0) appears after one or more black balls (1), those balls must cross each other through adjacent swaps. While scanning the string from left to right, keep a counter of how many black balls you have seen so far. When you encounter a white ball, it needs to swap past all previously seen black balls, so you add that count to the answer. This effectively counts the number of inversions where 1 appears before 0. The algorithm performs a single linear pass over the string and uses a simple greedy accumulation strategy.
This approach works because each misplaced pair must be swapped exactly once in an optimal arrangement. There is no benefit in delaying swaps or performing extra movements. The greedy counting directly models the minimum number of required adjacent swaps.
Approach 2: Prefix Sum and Two-Pointer Optimization (O(n) time, O(n) space)
Another way to reason about the problem is by precomputing how many black balls exist before each index. Build a prefix array where prefix[i] stores the count of 1s from the start up to index i. Then iterate through the string and whenever you encounter a white ball (0), add prefix[i] to the total swaps because those black balls must move to the right of it. This approach uses the same inversion idea but expresses it through prefix sums.
You can also view the process through a two pointers perspective: one pointer tracks where the next white ball should land while the scan pointer moves across the string. Each displacement contributes to the swap count. Although the prefix array is not strictly necessary, it can make the reasoning clearer when explaining the algorithm in interviews.
Recommended for interviews: The greedy single-pass solution is what most interviewers expect. It demonstrates strong understanding of greedy reasoning and inversion counting while keeping both time complexity O(n) and space complexity O(1). Showing the prefix-sum interpretation can reinforce your reasoning, but the greedy counter is the cleanest and most efficient implementation.
Approach 1: Greedy Approach
In this approach, we will calculate the number of swaps needed to move all black balls to the right in a greedy manner. We iterate through the string and count the mismatches where a black ball (1) is found at a position where it should be a white ball (0). The goal is to minimize these mismatches by swapping the black balls with whites whenever necessary.
def min_swaps(s):
n = len(s)
white_count = 0
swaps = 0
for i in range(n):
if s[i] == '0':
white_count += 1
else:
swaps += white_count
return swaps
# Example usage
print(min_swaps("101")) # Output: 1
print(min_swaps("100")) # Output: 2
print(min_swaps("0111")) # Output: 0public class MinSwaps {
public static int minSwaps(String s) {
int whiteCount = 0;
int swaps = 0;
for (char c : s.toCharArray()) {
if (c == '0') {
whiteCount++;
} else {
swaps += whiteCount;
}
}
return swaps;
}
public static void main(String[] args) {
System.out.println(minSwaps("101")); // Output: 1
System.out.println(minSwaps("100")); // Output: 2
System.out.println(minSwaps("0111")); // Output: 0
}
}#include <iostream>
#include <string>
int minSwaps(const std::string &s) {
int whiteCount = 0;
int swaps = 0;
for (char c : s) {
if (c == '0') {
++whiteCount;
} else {
swaps += whiteCount;
}
}
return swaps;
}
int main() {
std::cout << minSwaps("101") << std::endl; // Output: 1
std::cout << minSwaps("100") << std::endl; // Output: 2
std::cout << minSwaps("0111") << std::endl; // Output: 0
return 0;
}function minSwaps(s) {
let whiteCount = 0;
let swaps = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] === '0') {
whiteCount++;
} else {
swaps += whiteCount;
}
}
return swaps;
}
// Example usage
console.log(minSwaps("101")); // Output: 1
console.log(minSwaps("100")); // Output: 2
console.log(minSwaps("0111")); // Output: 0#include <stdio.h>
#include <string.h>
int minSwaps(char* s) {
int whiteCount = 0;
int swaps = 0;
for (int i = 0; s[i] != '\0'; ++i) {
if (s[i] == '0') {
++whiteCount;
} else {
swaps += whiteCount;
}
}
return swaps;
}
int main() {
printf("%d\n", minSwaps("101")); // Output: 1
printf("%d\n", minSwaps("100")); // Output: 2
printf("%d\n", minSwaps("0111")); // Output: 0
return 0;
}using System;
public class MinSwaps {
public static int MinSwaps(string s) {
int whiteCount = 0;
int swaps = 0;
foreach (char c in s) {
if (c == '0') {
whiteCount++;
} else {
swaps += whiteCount;
}
}
return swaps;
}
public static void Main() {
Console.WriteLine(MinSwaps("101")); // Output: 1
Console.WriteLine(MinSwaps("100")); // Output: 2
Console.WriteLine(MinSwaps("0111")); // Output: 0
}
}The function iterates over the string and counts the number of white balls ('0') it encounters. Each time a black ball ('1') is encountered, it adds the current count of white balls to the swap count, reflecting the swaps needed to move this black ball past all the white balls encountered so far.
Time Complexity: O(n) since we traverse the string once.
Space Complexity: O(1) since we are using only a constant amount of extra space.
Approach 2: Prefix Sum and Two-Pointer Optimization
This method utilizes a prefix sum array to keep track of the cumulative number of zeros up to each position in the string. A two-pointer approach then helps determine the best partition where all black balls should be on the right and all white balls should be on the left. This can help optimize the number of swaps by dynamically computing the transitions required at each potential partition.
def min_swaps(s):
n = len(s)
prefix_zeros = [0] * (n + 1)
# Fill prefix_zeros
for i in range(n):
prefix_zeros[i + 1] = prefix_zeros[i] + (1 if s[i] == '0' else 0)
total_ones = s.count('1')
min_swaps = float('inf')
# Try each position as the start of the right segment of 1s
for k in range(total_ones, n + 1):
ones_in_segment = total_ones - (prefix_zeros[k] - prefix_zeros[k - total_ones])
min_swaps = min(min_swaps, ones_in_segment)
return min_swaps
# Example usage
print(min_swaps("101")) # Output: 1
print(min_swaps("100")) # Output: 2
print(min_swaps("0111")) # Output: 0public class MinSwaps {
public static int minSwaps(String s) {
int n = s.length();
int[] prefixZeros = new int[n + 1];
for (int i = 0; i < n; i++) {
prefixZeros[i + 1] = prefixZeros[i] + (s.charAt(i) == '0' ? 1 : 0);
}
int totalOnes = (int) s.chars().filter(c -> c == '1').count();
int minSwaps = Integer.MAX_VALUE;
for (int k = totalOnes; k <= n; k++) {
int onesInSegment = totalOnes - (prefixZeros[k] - prefixZeros[k - totalOnes]);
minSwaps = Math.min(minSwaps, onesInSegment);
}
return minSwaps;
}
public static void main(String[] args) {
System.out.println(minSwaps("101")); // Output: 1
System.out.println(minSwaps("100")); // Output: 2
System.out.println(minSwaps("0111")); // Output: 0
}
}#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
int minSwaps(const std::string &s) {
int n = s.length();
std::vector<int> prefixZeros(n + 1, 0);
for (int i = 0; i < n; ++i) {
prefixZeros[i + 1] = prefixZeros[i] + (s[i] == '0');
}
int totalOnes = std::count(s.begin(), s.end(), '1');
int minSwaps = INT_MAX;
for (int k = totalOnes; k <= n; ++k) {
int onesInSegment = totalOnes - (prefixZeros[k] - prefixZeros[k - totalOnes]);
minSwaps = std::min(minSwaps, onesInSegment);
}
return minSwaps;
}
int main() {
std::cout << minSwaps("101") << std::endl; // Output: 1
std::cout << minSwaps("100") << std::endl; // Output: 2
std::cout << minSwaps("0111") << std::endl; // Output: 0
return 0;
}function minSwaps(s) {
const n = s.length;
const prefixZeros = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
prefixZeros[i + 1] = prefixZeros[i] + (s[i] === '0' ? 1 : 0);
}
const totalOnes = s.split('').filter(x => x === '1').length;
let minSwaps = Number.POSITIVE_INFINITY;
for (let k = totalOnes; k <= n; k++) {
const onesInSegment = totalOnes - (prefixZeros[k] - prefixZeros[k - totalOnes]);
minSwaps = Math.min(minSwaps, onesInSegment);
}
return minSwaps;
}
// Example usage
console.log(minSwaps("101")); // Output: 1
console.log(minSwaps("100")); // Output: 2
console.log(minSwaps("0111")); // Output: 0#include <stdio.h>
#include <string.h>
int minSwaps(char* s) {
int n = strlen(s);
int *prefixZeros = (int*)calloc(n + 1, sizeof(int));
for (int i = 0; i < n; ++i) {
prefixZeros[i + 1] = prefixZeros[i] + (s[i] == '0');
}
int totalOnes = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '1') totalOnes++;
}
int minSwaps = n;
for (int k = totalOnes; k <= n; ++k) {
int onesInSegment = totalOnes - (prefixZeros[k] - prefixZeros[k - totalOnes]);
if (onesInSegment < minSwaps) minSwaps = onesInSegment;
}
free(prefixZeros);
return minSwaps;
}
int main() {
printf("%d\n", minSwaps("101")); // Output: 1
printf("%d\n", minSwaps("100")); // Output: 2
printf("%d\n", minSwaps("0111")); // Output: 0
return 0;
}using System;
using System.Linq;
public class MinSwaps {
public static int MinSwaps(string s) {
int n = s.Length;
int[] prefixZeros = new int[n + 1];
for (int i = 0; i < n; i++) {
prefixZeros[i + 1] = prefixZeros[i] + (s[i] == '0' ? 1 : 0);
}
int totalOnes = s.Count(c => c == '1');
int minSwaps = int.MaxValue;
for (int k = totalOnes; k <= n; k++) {
int onesInSegment = totalOnes - (prefixZeros[k] - prefixZeros[k - totalOnes]);
minSwaps = Math.Min(minSwaps, onesInSegment);
}
return minSwaps;
}
public static void Main() {
Console.WriteLine(MinSwaps("101")); // Output: 1
Console.WriteLine(MinSwaps("100")); // Output: 2
Console.WriteLine(MinSwaps("0111")); // Output: 0
}
}This implementation calculates the prefix sum of zeros to optimize the determination of segments with fewer 1s that need to be swapped to reorder the sequence.
Time Complexity: O(n), since calculating the prefix sums and iterating through segment starts is linear.
Space Complexity: O(n) due to the storage of the prefix sum array.
Approach 3: 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.
We traverse the string from right to left. If the current position is '1', then we increment cnt by one, and add n - i - cnt to ans, where n is the length of the string. Finally, we return ans.
The time complexity is O(n), where n is the length of the string. The space complexity is O(1).
function minimumSteps(s: string): number {
const n = s.length;
let [ans, cnt] = [0, 0];
for (let i = n - 1; ~i; --i) {
if (s[i] === '1') {
++cnt;
ans += n - i - cnt;
}
}
return ans;
}func minimumSteps(s string) (ans int64) {
n := len(s)
cnt := 0
for i := n - 1; i >= 0; i-- {
if s[i] == '1' {
cnt++
ans += int64(n - i - cnt)
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n) since we traverse the string once. |
| Prefix Sum and Two-Pointer Optimization | Time Complexity: O(n), since calculating the prefix sums and iterating through segment starts is linear. |
| Counting Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Counting | O(n) | O(1) | Best general solution. Single pass with constant memory. |
| Prefix Sum + Two-Pointer Reasoning | O(n) | O(n) | Useful for explaining inversion logic or when prefix counts are already available. |
Frequently asked questions
Is Separate Black and White Balls easy or hard?
Separate Black and White Balls is classified as a Medium problem. The coding itself is simple, but the key challenge is recognizing that the answer equals the number of inversions where a black ball appears before a white ball.
Separate Black and White Balls Python/Java solution
The implementation is straightforward in Python, Java, C++, or JavaScript. Iterate through the string, increment a counter when you see '1', and add that counter to the answer whenever you see '0'. This produces the minimum number of adjacent swaps.
How to solve Separate Black and White Balls in O(n)?
Traverse the string from left to right and maintain a counter for how many 1s have been seen. Whenever you encounter a 0, add the current count of 1s to the result because that many swaps are required to move the white ball left. Continue until the end of the string to accumulate the minimum swaps.
What is the best approach for Separate Black and White Balls?
The greedy counting approach is the most efficient. Scan the string once while tracking how many black balls (1s) have appeared. Every time a white ball (0) appears, add the number of previous black balls to the swap count. This counts the minimum adjacent swaps required and runs in O(n) time with O(1) space.
Is Separate Black and White Balls asked at Google/Amazon/Meta?
Problems involving inversion counting, greedy swaps, and binary string rearrangement frequently appear in interviews at companies like Amazon, Google, and Meta. This problem tests your ability to recognize inversion patterns and design an O(n) greedy solution.
What data structure is used in Separate Black and White Balls?
The optimal approach only uses a few integer counters while scanning the string. Some explanations also use a prefix sum array to store the number of black balls before each index, but the greedy method works without additional data structures.
What is the time complexity of Separate Black and White Balls?
The optimal solution runs in O(n) time where n is the length of the string. The algorithm performs a single linear scan and only keeps a counter for previously seen black balls. Space complexity is O(1) because no extra data structures are required.