1151. Minimum Swaps to Group All 1's Together π
Description
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 are 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].
Constraints:
1 <= data.length <= 105
data[i]
is either0
or1
.
Solutions
Solution 1: Sliding Window
First, we count the number of $1$s in the array, denoted as $k$. Then we use a sliding window of size $k$, moving the right boundary of the window from left to right, and count the number of $1$s in the window, denoted as $t$. Each time we move the window, we update the value of $t$. Finally, when the right boundary of the window moves to the end of the array, the number of $1$s in the window is the maximum, denoted as $mx$. The final answer is $k - mx$.
The time complexity is $O(n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the array.
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |