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 <= 105nums[i] is either 0 or 1.The goal is to find the minimum number of swaps needed to group all 1's together. First, count the total number of 1's, which determines the window size you are interested in. Use the sliding window technique to find the window with the maximum number of 1's. This will ensure that the remaining positions in this window must be filled with 1's by swapping.
Since the array is circular, concatenate the array with itself to simulate the wrap-around. Slide a window of the calculated size and keep track of the maximum number of 1's within this window. To minimize swaps, the window should contain the maximum possible 1's.
This C solution uses a sliding window method adapted for a circular array by processing a concatenated array. We calculate the number of swaps needed as the difference between the total number of 1's and the maximum number of 1's found within any sliding window of size equal to the total number of 1's. We iterate twice the array length, using modulus to simulate the circular part and effectively sliding over the concatenated version.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the size of the array, due to the sliding window.
Space Complexity: O(1), because the space used does not scale with input size.
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 II with our built-in code editor and test cases.
Practice on FleetCode