Sort a binary array in Javascript without using extra spaces and having O(n) time complexity

One of the basic questions which are generally asked in technical interviews is to sort a given array which contains only 0 and 1 as elements without using another array and having a time complexity of O(n)

Example -
Input: [1, 0, 1, 0, 1, 0, 1, 0]
Output: [0, 0, 0, 0, 1, 1, 1, 1]

After reading O(n) the first thing that would come to mind is quick sort but having a binary array as an input makes the problem simpler for us. Let me share 2 methods to do it. But wouldn't you like to think of a pseudo-code before checking the solutions below?

Method 1 -

We count the number of zeros and ones in the array and then repopulate the array based on the count.

const sortBinaryArr = (arr) => { let zerosCount = 0; let arrLen = arr.length; // Iterate over the array once to get the count of the number of zeros preset for (let index = 0; index < arrLen; index++) { if (arr[index] === 0) { ++zerosCount; } } // Iterate over the array till the number of zeros we got above and set all array elements up to this index to zero for (let index = 0; index < zerosCount; index++) { arr[index] = 0; } // Iterate over the remaining items and set them to one for (let index = zerosCount; index < arrLen; index++) { arr[index] = 1; } return arr; }; 

Technically we are iterating over the array twice hence these operations combined are O(2n). Therefore the function sortBinaryArr() is an O(2 * n) operation, which is equivalent to O(n).

Method 2 -

A more optimized method is as below.

const sortBinaryArr = (arr) => { let pointer = -1; const arrLen = arr.length; for (let index = 0; index < arrLen; index++) { // if the number is smaller than 1 then swap it with the number at the pointer index if (arr[index] < 1) { pointer++; const temp = arr[pointer]; arr[pointer] = arr[index]; arr[index] = temp; } } return arr; }; 

The algorithm is pretty simple and self-explanatory. Here, we make use of a variable which acts as a pointer and helps us to keep track of zeros and ones while we iterate over the array.

Such that,

1. If the element is 0 then we increment the pointer by 1 and swap the current element with the element at the pointer position.
2. If the element is 1 we continue without any action.

Can you think of a better solution? Comment down your solution...