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

[Python] Underscore ‘_’ 의 목적

Python Comments vs Docstrings

Notes on Migrating Data from One Database to Another

Fluttering On Rails: Part 2 Create Action, Item Params & Flutter HTTP Request

How we quote technology

How to run Python scripts as a Windows service

An Introduction to Python Variables, Memory, and Reference Count

DevOps Meets Observability

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

new* | JS | Search Suggestions System | | Auto-complete feature using Trie | Coding Roun

Epam Interview Experience(12/27/2021)

Journey of DLithe Bootcamp Java Full Stack Developer | Week 7(May2-May 8)

Interact with Rest And Koa JS