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'.In this approach, we will calculate the number of swaps needed to move all black balls to the right in a greedy manner. We iterate through the string and count the mismatches where a black ball (1) is found at a position where it should be a white ball (0). The goal is to minimize these mismatches by swapping the black balls with whites whenever necessary.
The function iterates over the string and counts the number of white balls ('0') it encounters. Each time a black ball ('1') is encountered, it adds the current count of white balls to the swap count, reflecting the swaps needed to move this black ball past all the white balls encountered so far.
JavaScript
Java
C++
C
C#
Time Complexity: O(n) since we traverse the string once.
Space Complexity: O(1) since we are using only a constant amount of extra space.
This method utilizes a prefix sum array to keep track of the cumulative number of zeros up to each position in the string. A two-pointer approach then helps determine the best partition where all black balls should be on the right and all white balls should be on the left. This can help optimize the number of swaps by dynamically computing the transitions required at each potential partition.
This implementation calculates the prefix sum of zeros to optimize the determination of segments with fewer 1s that need to be swapped to reorder the sequence.
JavaScript
Java
C++
C
C#
Time Complexity: O(n), since calculating the prefix sums and iterating through segment starts is linear.
Space Complexity: O(n) due to the storage of the prefix sum array.
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n) since we traverse the string once. |
| Prefix Sum and Two-Pointer Optimization | Time Complexity: O(n), since calculating the prefix sums and iterating through segment starts is linear. |
Separate Black and White Balls - Leetcode 2938 - Python • NeetCodeIO • 10,544 views views
Watch 9 more video solutions →Practice Separate Black and White Balls with our built-in code editor and test cases.
Practice on FleetCode