⚡Flashcard Drill➔
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

  1. Every white ball must end up to the left of every black ball.
  2. Scan left to right and count the black balls seen so far, ones.
  3. Whenever a white ball is encountered, it must cross all ones black balls to its left, contributing ones swaps.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems