Minimum Swaps To Group All 1s Together Ii - Leetcode Solution

Problem Description: You are given a binary array nums of length n with at least one 1's present in it. 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: nums = [1,0,1,0,1] Output: 1 Explanation: There are 3 ways to group all 1's together: [1,1,1,0,0] swaps = 1 [0,1,1,1,0] swaps = 1 [0,0,1,1,1] swaps = 2 The minimum is 1.

Example 2: Input: nums = [0,0,0,1,0] Output: 0 Explanation: Since there is only one 1 in the array, no swaps needed.

Example 3: Input: nums = [1,0,1,0,1,0,0,1,1,0,1] Output: 2

Approach:

1. Find the number of 1's in the input array nums.
2. Initialize two pointers left and right. Left pointer denotes the beginning of a window of size same as the number of 1's and right pointer denotes the end of that window.
3. Traverse the input array nums, if the element at current index is 1, increment the count of one's. Continue till we find number of ones equal to the window size. Now, there are two conditions for counting the minimum swaps needed. If the window size is same as the number of ones present in the input array, there is no need to swap as all the ones are already together. If the window size is lesser than the number of ones present, we need to find the minimum swaps needed to make all the ones together in the current window.
4. To find the minimum swaps needed for the current window, initialize a variable count to 0. Traverse through the window between left and right pointers. If you find an element which is 0 and present in the window, increment count variable. Find the minimum value obtained by adding count to the number of zeroes in the array outside the current window. This gives the minimum number of swaps needed to bring the current 0 to the left end and the next (number of 1s in the window) number of ones to the right end. Add the minimum swaps needed into the answer variable. Increment the left pointer and decrement count if the leftmost element in the window is 0.
5. Return the answer variable which give the minimum swaps needed to bring all the 1s together in the array.

Solution:

class Solution { public: int minSwaps(vector<int>& nums) { int n = nums.size(), ones = 0, answer = n+1; for(int i=0;i<n;i++) if(nums[i]) ones++; if(ones<=1) return 0; int left = 0, count = 0; for(int right=0;right<n;right++) { if(nums[right]) count++; if(right-left+1==ones) { if(right<n-1) answer = min(answer, count+n-right-1-ones+count); else answer = min(answer, count); if(!nums[left]) count--; left++; } } return answer; } };

Time Complexity: O(n) Space Complexity: O(1)

1