0

I'm solving this problem where

Given an array of numbers, I need to move all zeros at the end of the array (in-place without making a copy of an array)

For example: given nums = [0, 1, 0, 3, 12]

After calling your function, nums should be [1, 3, 12, 0, 0].

My attempt:

   var moveZeroes = function(nums) {
      var count=0;
      
      //Remove anything that's not Zero.
      nums.forEach(function(val, index){
        if(val==0){
          nums.splice(index, 1);
          count++;
        }
      });
    
      //Fill in Zeros at the end
      for(var i=0; i< count ; i++){
        nums.push(0);
      }
    };
    
    
    var input1 = [0,1,0,3,12];
    var input2 = [0,0,1];
    
    moveZeroes(input1)
    console.log(input1); //Works!
    
    moveZeroes(input2)
    console.log(input2); //fails!

Issue:

It works with inputs like [0,1,0,3,12] but it fails in input such as [0,0,1] (The output I get is 0,1,0); Why? How can I fix it?

3
  • You ar cutting out (splicing) from an array that you are currently looping through Commented Mar 18, 2017 at 0:37
  • @ibrahimmahrir i guess you can do that.. I wasn't just tracking my previous element. Please check my answer that I posted. I just verified it and it works (passed all test cases) thanks for your time Commented Mar 18, 2017 at 0:40
  • The problem happens only if there is more successive 0s! Commented Mar 18, 2017 at 0:44

7 Answers 7

2

You ar cutting out (splicing) from an array that you are currently looping through (in the forEach), so it there is more successive 0 some of them will be skipped.

So if the array is [0, 0, 1] here is what happens:

forEach: (case of two or more successive 0s)

    [0, 0, 1]
//   ^ cursor is here (0 === 0 then remove it)
    [0, 1]
//      ^ cursor is at the second item, the second 0 is safe because it is now occupy a place that is already looped over
    [0, 1]
// fails

forEach: (case of no successive 0s)

    [0, 1, 0, 1]
//   ^ cursor is here (0 === 0 then remove it)
    [1, 0, 1]
//      ^ (0 === 0 then remove) 
    [1, 1]
// works

To solve the problem, you'll have to use a basic for loop where you can control the position of the cursor (index), or alter the array in a way that dosent change it's length and not hiding 0 behind the cursor like this:

var moveZeroes = function(nums) {
  nums.forEach(function(val, index) {
    if (val) {               // if it is a non-zero value
      nums.splice(index, 1); // remove it
      nums.unshift(val);     // add it to the begining of the array (note that the order of non-zero values will be reversed)
    }
  });
};


var input1 = [0, 1, 0, 3, 12];
var input2 = [0, 0, 1];

moveZeroes(input1)
console.log(input1); //Works!

moveZeroes(input2)
console.log(input2); // Now Works too!

Sign up to request clarification or add additional context in comments.

1 Comment

If the order of the non zeroes is reversed, it doesn't meet the spec
2

In-place solution: In order to shift all zeros rightwards, we iterate through the array keeping track of the last non-zero element's index i and shifting all non-zero elements to the left:

// Moves zeroes to the right:
function moveZeroes(array) {
  let i = 0;
  for (let j = 0; j < array.length; ++j) {
    if (i < j) array[i] = array[j];
    if (array[j] != 0) ++i;
  }
  return array.fill(0, i);
}

// Example:
console.log(moveZeroes([0, 1, 0, 3, 12]));

Explanation: We start with i and j pointing to the first array element. Now we traverse the array elements from left to right. Whenever we encounter a zero, we only increment j but not i. Thus, the difference between i and j is equal to the number of zeros in the array up to j. Now the trick: In order to move zeros to the right, we actually need to move all non-zero to the left. How much to the left? Exactly the amount of zeros we encountered so far. This is done by array[i] = array[j]. At the end, the remaining space between the last non-zero element at i and the end is filled with zeros.

Both operations - swapping values and filling with zero - are performed in-place, while splicing and pushing are usually not considered in-place as they change the array size and possibly memory location.

2 Comments

Can you explain your solution a little bit? Would be easier to understand :-) Thanks so much!
@TechnoCorner Added an explanation. Feel free to request further clarification in case I left something out.
1

here is an other implementation for it if you are interested . with a simple for loop

var moveZeroes = function(nums) {
     var res = []
     var count=0
     for(var i = 0 ; i < nums.length ; i++){
        nums[i] == 0 ? count += 1 : res.push(nums[i])
     }

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

    return res
};


    var input1 = [0,1,0,3,12];
    var input2 = [0,0,1];

    console.log(moveZeroes(input1))

    console.log(moveZeroes(input2))

Comments

1

index is not updated when you delete an item in an array.use for loop instead.

var moveZeroes = function(nums) {
  var count=0;

  //Remove anything that's not Zero.
  for(var index=0;index<nums.length;index++){     
    if(nums[index]==0){
      //when remove item from the array,the rest items index after removed item changed.
     //so you must change the index variable in the loop via:index--.
      nums.splice(index--, 1);
      count++;
    }
  };

  //Fill in Zeros at the end
  for(var i=0; i< count ; i++){
    nums.push(0);
  }
};


var input1 = [0,1,0,3,12];
var input2 = [0,0,1];

moveZeroes(input1)
console.log(input1); //Works!

moveZeroes(input2)
console.log(input2); //Works too!

2 Comments

You should mention the importance of doing index-- when you splice.
@Barmar thanks,I have updated my answer by add comment to describe why index--
0

I think i got it. Whenever we do "Splice" we are changing the array size, hence in the second example, we need to also check the previous element.

The completed code is/as follows:

var moveZeroes = function(nums) {
  var count=0;

  nums.forEach(function(val, index){
    if(val==0){
      nums.splice(index, 1);
      count++;
    }

    if(nums[index-1] == 0){
        nums.splice(index-1, 1);
        count++;
    }
  });

  for(var i=0; i< count ; i++){
    nums.push(0);
  }
};

1 Comment

Usually, in-place refers to keeping the array intact in memory without changing it's size during the operation.
0

The problem is that you're modifying the array while you're looping over it. Every time you splice out an element, all the elements after it get shifted down. But the next iteration goes to the next element, so it skips the element that was moved into the place of the element that was removed. The first example seems to work because you don't have two 0 in a row in the array, so skipping the next element doesn't cause a problem. The second example has two 0 in a row, so it skips the second one of the pair.

The simplest way to solve problems like this is to iterate in the reverse direction.

var moveZeroes = function(nums) {
      for (var i = nums.length-1; i >= 0; i--) {
        if (nums[i] == 0) {
          nums.splice(i, 1);
          nums.push(0);
        }
      }
    };
    
    
    var input1 = [0,1,0,3,12];
    var input2 = [0,0,1];
    
    moveZeroes(input1)
    console.log(input1); //Works!
    
    moveZeroes(input2)
    console.log(input2); //fails!

Comments

0

As others have already mentioned, you are removing elements from an array you are iterating over. This causes the index provided in the forEach function (that is iterating over the original version of the array) to be out of the date with the current updated array.

Here is one approach using the filter function:

var moveZeroesToEnd = function(nums) {
  var nonZeros = nums.filter(function(num) {
    return num != 0;
  });
  var zeros = nums.filter(function(num) {
    return num == 0;
  });
  return nonZeros.concat(zeros);
};


var input1 = [0, 1, 0, 3, 12];
var input2 = [0, 0, 1];

console.log(moveZeroesToEnd(input1))

console.log(moveZeroesToEnd(input2));

If you only want to loop through the array once, you could do:

var moveZeroesToEnd = function(nums) {
  var nonZeros = [];
  var zeros = [];
  nums.forEach(function(num) {
    var arr = num ? nonZeros : zeros;
    arr.push(num);
  });
  return nonZeros.concat(zeros);
};


var input1 = [0, 1, 0, 3, 12];
var input2 = [0, 0, 1];

console.log(moveZeroesToEnd(input1))

console.log(moveZeroesToEnd(input2));

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.