how to move all zero item in beginning in array?

user_5711656 0
Viewed 138

I am trying to solve a problem in O(n) without taking space (like map of object).I want to shift all zeros in beginning , one's in last and two's in middle.

input : [0, 1, 0, 2, 1] Expected output : [0,0,2,1,1] here is my code

let arr = [0, 1, 0, 2, 1];

function swap(input, i, j) {
    let temp = input[i];
    input[j] = input[i];
    input[i] = temp;
}

function moveZeroOneAndTwo(input) {
    let i = 0,
        j = input.length - 1;
    while (i < j) {
        while (arr[i] !== 0) i++;
        while (arr[j] !== 0) j--;

        swap(arr, j, i);
        i++;
        j--;
    }

return input
}

console.log(moveZeroOneAndTwo(arr))

I am trying to find 1 index from left and zero index from right and swap them still not able to solve this question

data-structures algorithm javascript
5 Answers

Count the 0,1,2 and than fill the array with the 3 values and their counts from the beginnig..
You don't need any aditional var-space and just use the original array.

let arr = [0, 1, 0, 2, 1];
let count = [0,0,0];
arr.forEach(el => count[el]++);
arr.fill(0,0,count[0]);
arr.fill(2,count[0],count[0]+count[2]);
arr.fill(1,count[0]+count[2],count[0]+count[1]+count[2]);
console.log(arr);

user_53245110

You could use the algorithm of the Dutch national flag problem

The Dutch national flag problem 1 is a computer science programming problem proposed by Edsger Dijkstra (In a chapter of his book A Discipline of Programming Prentice-Hall, 1976). The flag of the Netherlands consists of three colors: red, white and blue. Given balls of these three colors arranged randomly in a line (the actual number of balls does not matter), the task is to arrange them such that all balls of the same color are together and their collective color groups are in the correct order.

with a wrapper for the values.

var array = [0, 1, 0, 2, 1],
    values = [0, 2, 1],
    MID = 2,
    i = 0,
    j = 0,
    n = array.length - 1;

while (j <= n) {
    if (values[array[j]] < values[MID]) {
        [array[i], array[j]] = [array[j], array[i]];
        i++;
        j++;
    } else if (values[array[j]] > values[MID]) {
        [array[n], array[j]] = [array[j], array[n]];
        n--;
    } else {
        j++;
    }
}

console.log(array);

user_14476750

The easiest way is to scan the array from left to right and count both 0s and 1s. Then, assign 0 to the first zero_count number, 1 to the last one_count number and 2 to the others.

user_76449780

Perhaps not as elegant as Dijkstra's solution but I did come up with it myself. The idea is to keep one pointer, r, to the leftmost non-1 in the 1s section (on the right), and one pointer, l, to the rightmost 0 in the 0s section (on the left).

Now scan up:

If the value is 1, switch it with the value at the right pointer and lower that pointer; additionally, if we now have a 0 in hand, switch it with the value to the right of the left pointer and advance that pointer.

Otherwise, if the value is 0, switch it with the value to the right of the left pointer and advance that pointer.

(We have an additional check on each iteration to also increment or decrement the left or right pointers, respectively, if their section has increased.)

Clearly, it is O(n) since at every iteration we either increase i or decrease r, or we have sections that have made the iteration moot.

Seems to pass the control testing at the end.

function f(A){
  let l = -1;
  let r = A.length - 1;
  
  for (let i=0; i<=r; i++){
    if (A[r] == 1){
      r--;
      i--;

    } else if (A[l+1] == 0){
      l++;
      i--;

    } else if (A[i] == 1){
      [A[i], A[r]] = [A[r], A[i]];
      r--;
      if (A[i] == 0){
        [A[i], A[l+1]] = [A[l+1], A[i]];
        l++;
      }
      
    } else if (A[i] == 0 && i > l + 1){
      [A[i], A[l+1]] = [A[l+1], A[i]];
      l++;
    }
  }
}

function control(arr){
  let count = [0,0,0];
  arr.forEach(el => count[el]++);
  arr.fill(0,0,count[0]);
  arr.fill(2,count[0],count[0]+count[2]);
  arr.fill(1,count[0]+count[2],count[0]+count[1]+count[2]);
}

var As = [
  [0,1,0,2,1],
  [0,1,0,1,2,2,0],
  [1,0,0,1,2,2,2],
  [0,2,1,0,1,1,1],
  [0,2,2,1,1,0,0],
  [2,0,2,2,0,1,0],
  [2,0,0,2,2,0,0],
  [1,2,0,0,0,1,1],
  [1,0,2,1,2,1,0],
  [2,1,1,1,0,0,0],
  [1,2,2,2,0,0,0],
  [1,2,1,0,0,0,2],
  [1,2,0,0,1,1,2],
  [1,0,2,1,2,0,0],
  [2,0,1,0,2,2,1]
];

for (let A of As){
  console.log('' + A);
  f(A)
  console.log('' + A);
  console.log('');
}

var numTests = 500;
var n = 10;

for (let i=0; i<numTests; i++){
  let A1 = new Array(n);
  for (let j=0; j<n; j++)
    A1[j] = ~~(Math.random() * 3);
  let A1Pre = A1.slice();
  let A2 = A1.slice();
  f(A1);
  control(A2);
  if (String(A1) != String(A2)){
    console.log('Mismatch');
    console.log(String(A1Pre));
    console.log(String(A1));
    console.log(String(A2));
    break;
  }
}

user_20347870

Not so good at time complexity, but short:

const move0ToTheBeginning = arr => arr.sort((a, b) =>
  Math.abs(Math.sign(a)) - Math.abs(Math.sign(b))
)
user_141366770
Related