2938. Separate Black and White Balls

MediumView on LeetCode

Array Two Pointers Greedy

Time: O(n)

Space: O(1)

Intuition

Minimum swaps to group all 0s to left and all 1s to right. Count 1s in left half (should be 0s).

Algorithm

1Count total 1s = k. Sliding window of size k: minimum 0s in window = minimum swaps.

Common Pitfalls

•Swaps needed = 0s in the window of size (total 1s). Sliding window minimum.

2938.cs

// Approach: Count required swaps by tracking black balls encountered before each white position.
// Time: O(n) Space: O(1)

public class Solution
{
    public long MinimumSteps(string s)
    {
        long ans = 0;
        int ones = 0;

        foreach (char c in s)
        {
            if (c == '1')
                ones++;
            else // Move 1s to the front of the current '0'.
                ans += ones;
        }

        return ans;
    }
}

Was this solution helpful?