DDSA Solutions

2938. Separate Black and White Balls

MediumView on LeetCode
ArrayTwo PointersGreedy
Time: O(n)
Space: O(1)

Problem Overview

Minimum swaps to group all 0s to left and all 1s to right.

Intuition

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

Algorithm

  1. 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
C#
// 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?

Related Problems