NeetCode #773LC-2938MediumGreedy
← Back to All Problems#773 · #2938 · Separate Black and White Balls(区分黑球与白球)
📌 Problem Statement & Constraints
You are given a binary string
s where 1 is a black ball and 0 is a white ball. In one operation you may swap two adjacent balls. Return the minimum number of swaps to group all black balls to the right. Constraints: 1 <= s.length <= 10^5.💡 Core Algorithmic Approaches
- Every white ball must end up to the left of every black ball.
- Scan left to right and count the black balls seen so far,
ones. - Whenever a white ball is encountered, it must cross all
onesblack balls to its left, contributingonesswaps. - Summing these contributions counts each black-white inversion exactly once, which is the minimum.
💻 Benchmark Python3 Implementation
class Solution:
def minimumSteps(self, s: str) -> int:
res = 0
ones = 0
for c in s:
if c == "1":
ones += 1
else:
res += ones # this white crosses all preceding blacks
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): a single pass.
💾 Space Complexity
O(1): two counters.
⚠️ Interview Pitfalls & Follow-ups
- Counting inversions the other way: scanning right to left and counting zeros also works, but mixing the two directions double counts.
- Thinking a swap can move a ball more than one position: each operation moves a ball by exactly one, so the inversion count is the exact cost.
- Ignoring integer overflow in fixed-width languages: the answer can reach about
n^2 / 4 = 2.5 * 10^9; Python is safe. - Sorting the string: that would not count the adjacent-swap distance.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.