CODEWITHSUNDEEP
javascriptalgorithmsortingarray-algorithms
Faizal Mohaideen Kadersha
Faizal Mohaideen Kadersha

Reputation: 125

Weird bug in Javascript splice method

I have an array which contains "Zeros" and I want to move all of the "Zeros" to the last indexes of the array.

The expected output is: 

[1,2,3,0,0,0,0]

But instead I get:

[1,2,0,3,0,0,0]


let a = [0, 1, 2, 0, 0, 3, 0];
let count = 0;
let len = a.length;

for (i = 0; i < len; i++) {
  if (a[i] == 0) {
    count = count + 1;
    a.splice(i, 1);
  }
}

for (j = 0; j < count; j++) {
  a.push(0);
}

console.log(a);

Upvotes: 6

Views: 825

Answers (7)

גלעד ברקן
גלעד ברקן

Reputation: 23945

Note that each call to splice has generally O(n) complexity. There are many ways to instead achieve your desired result an order of magnitude more efficiently with a single O(n) iteration. Here's one:

let a = [0, 1, 2, 0, 0, 3, 0]

for (let i=0, j=0; j<a.length; j++)
  if (a[j] && i != j)
    [a[i++], a[j]] = [a[j], 0]

console.log(a)

Upvotes: 0

Nina Scholz
Nina Scholz

Reputation: 386680

Because splice changes the length of the array, you could iterate from the end of the array and splice the found value directly to the last index.

With this approach, you need only a single loop.

var a = [0, 1, 2, 0, 0, 3, 0],
    i = a.length;

while (i--) {
    if (a[i] === 0) {
        a.splice(a.length, 0, ...a.splice(i, 1));
    }
}

console.log(a);

A shorter approach without splicing - and starting from zero.

var a = [0, 1, 2, 0, 0, 3, 0],
    i, j = 0;

for (i = 0; i < a.length; i++) {
    if (a[i] !== 0) {
        [a[j], a[i]] = [a[i], a[j]]; // swap
        j++;
    }        
}

console.log(a);

Upvotes: 3

Fran&#231;ois Hupp&#233;
Fran&#231;ois Hupp&#233;

Reputation: 2116

You could add i--; and len--; each time you use splice:

let a = [0, 1, 2, 0, 0, 3, 0];
let count = 0;
let len = a.length;

for (i = 0; i < len; i++) {
  if (a[i] == 0) {
    count = count + 1;
    a.splice(i, 1);
    i--; len--;
  }
}

for (j = 0; j < count; j++) {
  a.push(0);
}

console.log(a);

This is because when you splice 1 element, the keys of the array are shifted down by one, so the key of the next element you want to check is the same as the one you just removed. The len is also corrected with len--; because we just removed an element.

While this answer is the correct way of doing this using your original plan, it is kind of a fix. Your problem was that you loop over an array, and that array loses elements during the loop, and generally the right approach in these situations is to loop backward. This way the elements that risks having their key changed during the loop are the elements we already checked.

Upvotes: 0

Thomas
Thomas

Reputation: 12657

Instead of splicing the Array over and over again, here is a different approach:

let a = [0, 1, 2, 0, 0, 3, 0];
// create some more (random) data
for (let i = a.length; i < 30; ++i)
  a[i] = Math.floor(Math.random() * Math.random() * 10);
console.log(""+a);

let i = 0, j = 0, len = a.length;
// move non-0 values to the front
while (i < len) {
  if (a[i] !== 0) {
    a[j++] = a[i];
  }
  ++i;
}
// fill the end of the list with 0
while (j < len) a[j++] = 0;

console.log(""+a);

Upvotes: 0

Hazem Nabil
Hazem Nabil

Reputation: 161

In the for loop when you splice the array the array and it length are changed.

for that you must fix the i in the for loop by subtract 1 

  i++;

and fix the length by subtract 1 or reget the length again 

let a = [0, 1, 2, 0, 0, 3, 0];
let count = 0;
let len = a.length;

for (i = 0; i < len; i++) {
  if (a[i] == 0) {
    count = count + 1;
    a.splice(i, 1);
    len = a.length;
    i--;
  }
}

for (j = 0; j < count; j++) {
  a.push(0);
}

console.log(a);

Upvotes: 1

sergdenisov
sergdenisov

Reputation: 8572

You can do it much simpler with Array.prototype.sort(): 

const array = [0, 1, 2, 0, 0, 3, 0];
const sortedArray = array.sort((a, b) => {
  if (a === 0) {
    return 1;
  }
  if (b === 0) {
    return -1;
  }
  return a - b;
});

console.log(sortedArray);

Upvotes: 1

John
John

Reputation: 3785

When you remove the item from the array all the element shift down by one. When you advance your index (i++), you skip the shifted down item in the array which happens to be successive zero in the array.

Solution: Do the for next loop backward and it'll work.

Upvotes: 9

Related Questions