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.
1def min_swaps(s):
2 n = len(s)
3 white_count = 0
4 swaps = 0
5 for i in range(n):
6 if s[i] == '0':
7 white_count += 1
8 else:
9 swaps += white_count
10 return swaps
11
12# Example usage
13print(min_swaps("101")) # Output: 1
14print(min_swaps("100")) # Output: 2
15print(min_swaps("0111")) # Output: 0The function iterates over the string and counts the number of white balls ('0') it encounters. Each time a black ball ('1') is encountered, it adds the current count of white balls to the swap count, reflecting the swaps needed to move this black ball past all the white balls encountered so far.
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).