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 <stdio.h>
2#include <string.h>
3
4int minSwaps(char* s) {
5 int whiteCount = 0;
6 int swaps = 0;
7 for (int i = 0; s[i] != '\0'; ++i) {
8 if (s[i] == '0') {
9 ++whiteCount;
10 } else {
11 swaps += whiteCount;
12 }
13 }
14 return swaps;
15}
16
17int main() {
18 printf("%d\n", minSwaps("101")); // Output: 1
19 printf("%d\n", minSwaps("100")); // Output: 2
20 printf("%d\n", minSwaps("0111")); // Output: 0
21 return 0;
22}In C, the solution involves iterating over each character in the string, counting the white balls, and updating the swap count accordingly.
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.
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.