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

--

--

--

The biggest power in the world is to be able to give life to something, and guess what? Code gives you this ability! Here in this publication, we build stuff, we share knowledge in tech, and share our stories, feel free to join — https://theleanprogrammer.com/writer-request/

Recommended from Medium

Arrays → In → Java

Recapitulation of BabySunCoin PROJECT AMA event held at AMA LOVERS CLUB.

Minimum Window Subsequence

Localization Changes in Java 9

Renovate: Dependency Management

Is GNOME Theming Dead ..or Not?

How to implement flow coordinator pattern

Use of @Async asynchronous method + @Transactional transaction processing

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
iAmSonika | www.startlearncoding.com

iAmSonika | www.startlearncoding.com

Working in Walmart as UI Developer | Mentor | React | JavaScript | HTML | CSS

More from Medium

My Experience at Oasis Infobyte as Web Development Intern.

Scrolling Along

keep single copy of node_modules for multiple projects

Understanding the work loop in React