Move from brute-force thinking to an efficient approach using two pointers strategy.
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'.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Two Pointers · Greedy
"101"
"100"
"0111"
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2938: Separate Black and White Balls
class Solution {
public long minimumSteps(String s) {
long ans = 0;
int cnt = 0;
int n = s.length();
for (int i = n - 1; i >= 0; --i) {
if (s.charAt(i) == '1') {
++cnt;
ans += n - i - cnt;
}
}
return ans;
}
}
// Accepted solution for LeetCode #2938: Separate Black and White Balls
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
}
# Accepted solution for LeetCode #2938: Separate Black and White Balls
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
// Accepted solution for LeetCode #2938: Separate Black and White Balls
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #2938: Separate Black and White Balls
// class Solution {
// public long minimumSteps(String s) {
// long ans = 0;
// int cnt = 0;
// int n = s.length();
// for (int i = n - 1; i >= 0; --i) {
// if (s.charAt(i) == '1') {
// ++cnt;
// ans += n - i - cnt;
// }
// }
// return ans;
// }
// }
// Accepted solution for LeetCode #2938: Separate Black and White Balls
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;
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair of elements. The outer loop picks one element, the inner loop scans the rest. For n elements that is n × (n−1)/2 comparisons = O(n²). No extra memory — just two loop variables.
Each pointer traverses the array at most once. With two pointers moving inward (or both moving right), the total number of steps is bounded by n. Each comparison is O(1), giving O(n) overall. No auxiliary data structures are needed — just two index variables.
Review these before coding to avoid predictable interview regressions.
Wrong move: Advancing both pointers shrinks the search space too aggressively and skips candidates.
Usually fails on: A valid pair can be skipped when only one side should move.
Fix: Move exactly one pointer per decision branch based on invariant.
Wrong move: Locally optimal choices may fail globally.
Usually fails on: Counterexamples appear on crafted input orderings.
Fix: Verify with exchange argument or monotonic objective before committing.