A swap is defined as taking two distinct positions in an array and swapping the values in them.
A circular array is defined as an array where we consider the first element and the last element to be adjacent.
Given a binary circular array nums
, return the minimum number of swaps required to group all 1
‘s present in the array together at any location.
Example 1:
Input: nums = [0,1,0,1,1,0,0] Output: 1 Explanation: Here are a few of the ways to group all the 1's together: [0,0,1,1,1,0,0] using 1 swap. [0,1,1,1,0,0,0] using 1 swap. [1,1,0,0,0,0,1] using 2 swaps (using the circular property of the array). There is no way to group all 1's together with 0 swaps. Thus, the minimum number of swaps required is 1.
Example 2:
Input: nums = [0,1,1,1,0,0,1,1,0] Output: 2 Explanation: Here are a few of the ways to group all the 1's together: [1,1,1,0,0,0,0,1,1] using 2 swaps (using the circular property of the array). [1,1,1,1,1,0,0,0,0] using 2 swaps. There is no way to group all 1's together with 0 or 1 swaps. Thus, the minimum number of swaps required is 2.
Example 3:
Input: nums = [1,1,0,0,1] Output: 0 Explanation: All the 1's are already grouped together due to the circular property of the array. Thus, the minimum number of swaps required is 0.
Constraints:
1 <= nums.length <= 105
nums[i]
is either0
or1
.
Solution: Sliding Window
Step 1: Count how many ones are there in the array. Assume it’s K.
Step 2: For each window of size k, count how many ones in the window, we have to swap 0s out with 1s to fill the window. ans = min(ans, k – ones).
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: int minSwaps(vector<int>& nums) { const int n = nums.size(); const int k = accumulate(begin(nums), end(nums), 0); int ans = INT_MAX; for (int i = 0, cur = 0; i < n + k; ++i) { if (i >= k) cur -= nums[(i - k + n) % n]; cur += nums[i % n]; ans = min(ans, k - cur); } return ans; } }; |