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 <= 105data[i] is either 0 or 1.First, we count the number of 1s 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 1s 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 1s 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.
Java
C++
Go
TypeScript
C#
Minimum Swaps to Group All 1's Together II - Leetcode 2134 - Python • NeetCodeIO • 17,380 views views
Watch 9 more video solutions →Practice Minimum Swaps to Group All 1's Together with our built-in code editor and test cases.
Practice on FleetCode