2938. Separate Black and White Balls
Problem Description
In this problem, we're given n
balls on a table, colored black or white, and represented by a binary string s
of length n
. The character 1
represents a black ball, while 0
represents a white ball. The objective is to group all the black balls to the right side of the string and all the white balls to the left side, using a series of adjacent swaps. Each step allows a swap of two neighboring balls. The final goal is to determine the minimum number of such swaps needed to achieve the segregation of the balls into their respective groups by color.
Intuition
The key insight behind the solution is to count the number of steps it takes to bring each black ball (represented by 1
) to its final position on the right side. Due to the nature of the swaps, every time we move a black ball one position to the right, one swap is required. However, as we progress in grouping the black balls to the right, each successive black ball we encounter will have to be moved a few positions less than the previous one because of the black balls that we have already moved.
To calculate the number of moves efficiently, we simulate this process in reverse order by iterating from the right to the left. We use a variable cnt
to keep track of the black balls that have been encountered, and we use ans
to sum up the moves needed. With every black ball encountered, we increase cnt
by one since one more black ball is now in its right-most position. We add n - i - cnt
to ans
each time we find a black ball because the ball needs to pass over n - i - cnt
black balls that have already been placed to the right.
By moving from right to left, we can calculate the minimum steps with a single pass through the string, making the process efficient and avoiding the need for simulating actual swaps.
Learn more about Greedy and Two Pointers patterns.
Solution Approach
The implementation of the solution starts by initializing two variables, cnt
and ans
, both set to 0. The variable cnt
will keep track of the number of black balls (1
s) we have encountered starting from the rightmost side, while ans
will accumulate the total number of steps (swaps) required to move all black balls to the right.
We begin with a reverse iteration of the string, from the last character to the first (index n-1
to 0
). We traverse in reverse because we're interested in calculating the number of steps a black ball needs to move from its current position to its final destination, which we can easily compute once we know how many black balls are already positioned to the right of it.
During the iteration, for each black ball we encounter, which is marked by a 1
in string s
:
- We increment
cnt
by 1, representing another black ball that is in its appropriate position on the right. - We calculate
n - i - cnt
, which gives us the number of swaps needed to move this particular black ball past thecnt
black balls already in place. Note thati
is the current index in the iteration. We do this because each black ball already placed means one less swap needed for the current one. - We add this calculated number of swaps to
ans
, which is our total.
The algorithm does not use auxiliary data structures, thereby maintaining a space complexity of O(1)
. The time complexity is O(n)
, as we only need to traverse the string once to count the necessary swaps.
Here's the reference approach, expressed as pseudocode to describe the process:
1function minimumSteps(s: string) -> integer: 2 n = length(s) 3 cnt = 0 4 ans = 0 5 for i from n-1 to 0: 6 if s[i] == '1': 7 cnt = cnt + 1 8 ans = ans + (n - i - cnt) 9 return ans
The beauty of this solution lies in its simplicity. By intelligently choosing to iterate in reverse and keep track of the number of encountered black balls, we can calculate the solution in a single pass without simulating the swaps, which could have been significantly costlier in terms of performance.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through an example to better understand the solution approach using the problem content above.
Imagine we have the binary string 10101
, representing 5 balls where the 1
s are black balls, and the 0
s are white balls. Using the solution approach, we want to calculate the minimum number of swaps needed to group all black balls to the right.
Following the steps of the algorithm:
- We start with
cnt
andans
initialized to 0. - The string
10101
has lengthn = 5
. - We iterate in reverse, starting from the last character (index 4) to the first (index 0).
- i = 4, s[4] =
1
(black ball): We incrementcnt
to 1.ans
becomesans + (5 - 4 - 1)
which isans + 0
(no swap needed because it is already in the last position). - i = 3, s[3] =
0
(white ball): No action taken because we only count swaps for black balls.cnt
andans
are unchanged. - i = 2, s[2] =
1
(black ball): We incrementcnt
to 2.ans
becomesans + (5 - 2 - 2)
which isans + 1
(one swap needed to move to the end). - i = 1, s[1] =
0
(white ball): Again, no action is needed for white balls. No changes tocnt
orans
. - i = 0, s[0] =
1
(black ball): Incrementcnt
to 3.ans
becomesans + (5 - 0 - 3)
which isans + 2
(two swaps needed to move to the end).
- i = 4, s[4] =
- Adding these up,
ans = 0 + 1 + 2
which equals3
.
Therefore, for the given string 10101
, it will take a minimum of 3 swaps to move all the black balls to the right side of the string. This matches the logic of our solution approach. The black balls initially at indices 0 and 2 need to each move past two white balls to reach the far right, with the last black ball at index 4 already in the correct position.
Solution Implementation
1class Solution:
2 def minimumSteps(self, s: str) -> int:
3 # Length of the given string
4 length = len(s)
5
6 # Initialize 'answer' for holding the minimum steps and
7 # 'one_count' for keeping track of the number of '1's encountered
8 answer = 0
9 one_count = 0
10
11 # Traverse the string in reverse from last to first character
12 for i in reversed(range(length)):
13 # Check if the current character is '1'
14 if s[i] == '1':
15 # If it's '1', increment the 'one_count'
16 one_count += 1
17 # Update answer by how many steps needed to move this '1' to the end
18 # considering the number of ones already counted.
19 answer += (length - i - 1) - one_count + 1
20
21 # Return the total minimum steps calculated
22 return answer
23
1class Solution {
2 /**
3 * Calculates the minimum number of steps to move all '1's to the right end of the string
4 *
5 * @param s the input string representing a binary number
6 * @return the minimum number of steps required
7 */
8 public long minimumSteps(String s) {
9 // Initialize the answer to 0
10 long answer = 0;
11 // Counter for the number of '1's found
12 int oneCount = 0;
13 // Length of the string
14 int length = s.length();
15
16 // Iterate over the string from right to left
17 for (int i = length - 1; i >= 0; --i) {
18 // Check if the current character is '1'
19 if (s.charAt(i) == '1') {
20 // Increase the count of '1's
21 ++oneCount;
22 // Add the number of steps to move this '1' to the right end
23 answer += length - i - oneCount;
24 }
25 }
26 // Return the total number of steps calculated
27 return answer;
28 }
29}
30
1#include <string>
2
3class Solution {
4public:
5 // Function to calculate the minimum number of steps required.
6 long long minimumSteps(std::string s) {
7 long long steps = 0; // Variable to store the minimum steps.
8 int onesCount = 0; // Counter for the occurrences of '1'.
9 int length = s.size(); // Get the size of the string.
10
11 // Traverse the string from the end to the beginning.
12 for (int i = length - 1; i >= 0; --i) {
13 if (s[i] == '1') { // If the current character is '1'.
14 ++onesCount; // Increment the count of '1's.
15
16 // Accumulate the distance from right-most end minus
17 // the number of '1's encountered so far.
18 steps += length - i - onesCount;
19 }
20 }
21 // Return the computed minimum steps.
22 return steps;
23 }
24};
25
1function minimumSteps(s: string): number {
2 const stringLength = s.length; // Get the length of the input string.
3 let steps = 0; // Initialize the steps counter to zero.
4 let countOfOnes = 0; // Initialize a counter to keep track of the number of '1's encountered.
5
6 // Iterate over the string in reverse order.
7 for (let i = stringLength - 1; i >= 0; --i) {
8 // The '~' before 'i' is a bitwise NOT operator, used here as a shorthand for (i !== -1).
9 if (s[i] === '1') {
10 // If the current character is '1', increment the count of '1's.
11 ++countOfOnes;
12 // Accumulate the necessary steps to bring the '1' to the end of the string, taking into account
13 // the count of '1's encountered so far, which do not need to be moved.
14 steps += stringLength - i - countOfOnes;
15 }
16 }
17
18 // Return the total number of steps required to move all '1's to the end of the string.
19 return steps;
20}
21
Time and Space Complexity
Time Complexity
The given code involves a single for-loop that iterates over the string s
in reverse order, starting from the last character to the first. Since each element of the string s
is processed exactly once during this iteration, the time complexity of this operation is O(n)
, where n
is the length of the string s
. Inside the loop, only constant time operations are performed (i.e., basic arithmetic operations and conditional checks), which do not depend on the size of the input, therefore they don't affect the overall linear time complexity.
Space Complexity
The algorithm uses a fixed number of variables (n
, ans
, cnt
, and i
) that do not scale with the size of the input. This implies that the space complexity is constant. Therefore, the space complexity of the code is O(1)
, as the amount of memory used does not increase with the size of the input string s
.
Learn more about how to find time and space complexity quickly using problem constraints.
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we