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.
1public class MinSwaps {
2 public static int minSwaps(String s) {
3 int whiteCount = 0;
4 int swaps = 0;
5 for (char c : s.toCharArray()) {
6 if (c == '0') {
7 whiteCount++;
8 } else {
9 swaps += whiteCount;
10 }
11 }
12 return swaps;
13 }
14
15 public static void main(String[] args) {
16 System.out.println(minSwaps("101")); // Output: 1
17 System.out.println(minSwaps("100")); // Output: 2
18 System.out.println(minSwaps("0111")); // Output: 0
19 }
20}The Java implementation uses the same logic, with a for-each loop iterating over the characters of the string. It tracks the number of white balls encountered to compute the minimum swaps needed.
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.
The Java solution uses an int array for prefix sums and checks possible start positions for the right group of black balls (1s).