2938. Separate Black and White Balls LeetCode Solution
In this guide, you will get 2938. Separate Black and White Balls LeetCode Solution with the best time and space complexity. The solution to Separate Black and White Balls problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Separate Black and White Balls
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.
Input: s = “0111”
Output: 0
Explanation: All the black balls are already grouped to the right.
Constraints:
1 <= n == s.length <= 105
s[i] is either '0' or '1'.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
2938. Separate Black and White Balls LeetCode Solution in C++
class Solution {
public:
long long minimumSteps(string s) {
long ans = 0;
int ones = 0;
for (const char c : s)
if (c == '1')
++ones;
else // Move 1s to the front of the current '0'.
ans += ones;
return ans;
}
}; /* code provided by PROGIEZ */
2938. Separate Black and White Balls LeetCode Solution in Java
class Solution {
public long minimumSteps(String s) {
long ans = 0;
int ones = 0;
for (final char c : s.toCharArray())
if (c == '1')
++ones;
else // Move 1s to the front of the current '0'.
ans += ones;
return ans;
}
} // code provided by PROGIEZ
2938. Separate Black and White Balls LeetCode Solution in Python
class Solution:
def minimumSteps(self, s: str) -> int:
ans = 0
ones = 0
for c in s:
if c == '1':
ones += 1
else: # Move 1s to the front of the current '0'.
ans += ones
return ans # code by PROGIEZ
