Sponsored
Sponsored
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.
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.
1#include <iostream>
2#include <string>
3
4int minSwaps(const std::string &s) {
5 int whiteCount = 0;
6 int swaps = 0;
7 for (char c : s) {
8 if (c == '0') {
9 ++whiteCount;
10 } else {
11 swaps += whiteCount;
12 }
13 }
14 return swaps;
15}
16
17int main() {
18 std::cout << minSwaps("101") << std::endl; // Output: 1
19 std::cout << minSwaps("100") << std::endl; // Output: 2
20 std::cout << minSwaps("0111") << std::endl; // Output: 0
21 return 0;
22}This C++ solution also implements a similar logic, accumulating the swaps required as we iterate over the string.
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.
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.
In this JavaScript solution, the prefix sum of zeros helps calculate how many ones need to be out of place for each potential segment of black balls.