Leetcode Diary: Move Zeros

https://leetcode.com/problems/move-zeroes/

the question is super easy if you solve it by using an extra array, using built-in methods to mutate the array via splice and then push.

However if you were to solve it in place like the question says, it isn't so easy anymore. This question is probably medium really because it requires some smart insights then.

I'll discuss my solution then another solution from the discussion section, which is actually much better, but very unintuitive (which is why I am writing this article)

My soultion was relatively simple: using two pointers, one for indexes that tracks zeros, and another for tracking non-zeros.
You write a while loop and while both indexes are less than the array length, you do:
1.) increment zeroIndex until you find the a 0 in the array
2.) increment the integerIndex while it's less than zeroIndex and the current number is a 0.
3.) both increments should stop if it is at array length
4.) swap these two indices
5.) repeat

code as below:

function swap (nums, i, j) {
    const temp = nums[i]
    nums[i] = nums[j]
    nums[j] = temp
}
var moveZeroes = function(nums) {
    let zeroIndex = 0
    let integerIndex = 0

    while (zeroIndex < nums.length && integerIndex < nums.length) {
        while ( nums[zeroIndex] !== 0 && 
            zeroIndex < nums.length
        ) {
            zeroIndex++
        }

        while (
            (
                nums[integerIndex] === 0 || 
                integerIndex < zeroIndex
            ) &&
            integerIndex < nums.length
        ) {
            integerIndex++
        }

        if (
            zeroIndex < nums.length && 
            integerIndex < nums.length
        ) {
            swap(nums, zeroIndex, integerIndex)
        }
    }
};

it's not great, especially with the number of conditions involved, but it works :) ...

now here is the fun part...

the intuition required to get the optimal solution is:
you need to move all numbers by some number, this number is determined by how many 0s are in front of it to start with

therefore in the same two pointers approach a much easier way to do this is by having one pointer that tracks the current iteration and the other for tracking how many 0s have appeared in the iteration.

for each 0, you increment the zero count
for each non-zero you move it upward by the current zero count.

const moveZeroes = function(nums) {
  let j =0;
  for(let i=0; i< nums.length;i++){
   if(nums[i] === 0){
      j++ ;
   } else { 
     [nums[i-j], nums[i]] = [nums[i], nums[i-j]] 
   }
  }
};

this is much easier to read, but definitely harder to understand how it works.

I think during an interview if you were with this problem, the best bet to get this intuition if you go through this question carefully, and count exactly how many 0s does the number need to move forward.
I'd definitely be okay if you were to come up with some more complicated solution like the former though :) ...