TheLeanProgrammer
Published in

TheLeanProgrammer

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;}

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store