Given a binary array data, return the minimum number of swaps required to group all 1’s present in the array together in any place in the array.
Example 1:
Input: data = [1,0,1,0,1] Output: 1 Explanation: There are 3 ways to group all 1's together: [1,1,1,0,0] using 1 swap. [0,1,1,1,0] using 2 swaps. [0,0,1,1,1] using 1 swap. The minimum is 1.
Example 2:
Input: data = [0,0,0,1,0] Output: 0 Explanation: Since there is only one 1 in the array, no swaps needed.
Example 3:
Input: data = [1,0,1,0,1,0,0,1,1,0,1] Output: 3 Explanation: One possible solution that uses 3 swaps is [0,0,0,0,0,1,1,1,1,1,1].
Example 4:
Input: data = [1,0,1,0,1,0,1,1,1,0,1,0,0,1,1,1,0,0,1,1,1,0,1,0,1,1,0,0,0,1,1,1,1,0,0,1] Output: 8
Constraints:
1 <= data.length <= 10^5data[i] is 0 or 1.
The description was taken from https://leetcode.com/problems/minimum-swaps-to-group-all-1s-together/.
#O(N) Time, O(1) Space
class Solution:
def minSwaps(self, data: List[int]) -> int:
ones = sum(data)
window, max_window = 0, 0
left, right = 0, 0
while right < len(data):
window += data[right]
right += 1
if right - left > ones:
window -= data[left]
left += 1
max_window = max(max_window, window)
return ones - max_windowThis solution isn't very intuitive at first.
If we are looking for the best spot to swap zeros for ones, that best spot will be a subarray with the most amount of ones and the least amount of zeros.
Now, if we are given a problem that requires looking for a specific subarray or sublist that follows a certain constraint, that makes the problem a candidate for a sliding window.
We will count how many ones are in the array total, and we will look for a window that can fit the remaining ones into it.
Let's start by counting the number of ones we have in the input array.
We can do this by summing the input.
ones = sum(data)
Let's then initialize our sliding window counter to tell us how many ones we have between the right and left pointers and the maximum window we have seen so far.
window, max_window = 0, 0
left, right = 0, 0
We will continue sliding our window until we have reached the end of the array.
while right < len(data):
We will start off by adding the number at the right pointer to the window counter within each iteration.
Then, we will expand the window.
window += data[right]
right += 1
Similar to traditional sliding window problems, we will expand our window until it no longer satisfies a given constraint and becomes invalid, in which case we will shrink the left side.
In this case, our window will no longer be valid if its length is greater than the number of ones we have. If that is the case, then we would be trying to fit more ones into the window than we have.
When that happens, we will shrink the window by excluding the left pointer's number and incrementing the left pointer.
if right - left > ones:
window -= data[left]
left += 1
Once we have a valid window, we will test it for the maximum window.
The maximum window will be the best subarray where the length is closest to the number of ones we have that also has the most ones and the least zeros, and we can get the frequency of ones and zeros within the window by summing the window as we did in the beginning.
This will allow us to find the cheapest swaps that we can perform.
[1,0,1,0,1,0,0,1,1,0,1]
[1,0,1,0,1,0,0,1,1,0,1]
[0,0,0,1,1,1,1,1,1,0,0], three swaps.
max_window = max(max_window, window)
Once we have found the best window that we could, the fewest amount of swaps will be how many ones we have in total minus the maximum window. This will give us how many zeros are in the window that we can swap the ones into.
return ones - max_window