JS |Minimum swaps to get together 1’s

Amazon Interview Question

Input : arr[] = [ 1, 0, 1, 0, 1 ]
Output : 1
Explanation: Only 1 swap is required to 
group all 1's together. Swapping index 1
and 4 will give arr[] = [1, 1, 1, 0, 0]

Input : arr[] = [1,0,1,0,1,0,0,1,1,0,1]
Output : 3 Swaps required

Efficient approach, using the concept of window-sliding technique(please go through this once)

• First count total number of 1’s in the array
• Suppose this count is x, now find the subarray of length x of this array with a maximum number of 1’s using the concept of window-sliding
• Maintain a variable to find the number of 1’s present in a subarray in O(1) extra space and for each sub-array maintain maxOnes Variable and at last Return numberOfZeros (numberOfZeroes = x — maxOnes)

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

function minSwaps(arr, n) {
let numberOfOnes = 0;
// find total number of all 1's in the array
for (let i = 0; i < n; i++) {
  if (arr[i] == 1) numberOfOnes++;
}
let x = numberOfOnes;
let count_ones = 0, maxOnes;
// Find 1's for first subarray of length x
for(let i = 0; i < x; i++){
   if(arr[i] == 1) count_ones++;
}
maxOnes = count_ones;
/** using sliding window technique to find max number of ones in subarray of length x **/
for (let i = 1; i <= n-x; i++) {
/** first remove leading element and check if it is equal to 1 then decrement the value of count_ones by 1 **/
   if (arr[i - 1] == 1)
     count_ones--;

/** Now add trailing element and check if it is equal to 1 Then increment the value of count_ones by 1 **/
   if(arr[i + x - 1] == 1)
     count_ones++;
   if (maxOnes < count_ones)
     maxOnes = count_ones;
   }
/ ** calculate number of zeros in subarray of length x with maximum number of 1’s **/
   let numberOfZeroes = x - maxOnes;
return numberOfZeroes;
}

• https://www.geeksforgeeks.org/minimum-swaps-required-group-1s-together/
• Follow me for more coding interviews.
• This problem is very popular in coding interviews.
• Keep learning, keep growing!
• Don’t forget to follow me for more such articles, and subscribe to our newsletter.
• Let’s connect on LinkedIn!. Please read more for more data structure javascript questions.

Don’t forget to follow The Lean Programmer Publication for more such articles, and subscribe to our newsletter tinyletter.com/TheLeanProgrammer