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.
1function minSwaps(s) {
2 let whiteCount = 0;
3 let swaps = 0;
4 for (let i = 0; i < s.length; i++) {
5 if (s[i] === '0') {
6 whiteCount++;
7 } else {
8 swaps += whiteCount;
9 }
10 }
11 return swaps;
12}
13
14// Example usage
15console.log(minSwaps("101")); // Output: 1
16console.log(minSwaps("100")); // Output: 2
17console.log(minSwaps("0111")); // Output: 0This JavaScript function implements the same logic as the Python solution. It counts the white balls and keeps track of the total number of swaps needed by adding the current count of white balls whenever a black ball is encountered.
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.
Using the C approach, we dynamically compute the prefix sums of zeros and analyze potential groupings of 1s to determine the minimum number of swaps.