Discussion on: JavaScript Challenge 3: Remove Zeroes

View post

So, before I see your solution, I want to try and figure it out for myself. This is basically a "sort in place" problem. So any sorting algorithm that can be done in a for loop should be feasible. I could use a temporary String, as it's not strictly forbidden, but I guess it's against the spirit of the rules, so I'll avoid that.

I'll be doing a lot of swapping, so:

function swap(arr, i1, i2)
{
  let temp = arr[i1];
  arr[i1] = arr[i2];
  arr[i2] = temp;
}

Then the algorithm should be relatively simple: if you haven't seen a zero yet, carry on, if you do see a zero, make a note of where it is, the next non-zero you see move ahead of that zero.

function put0AtTheBack(arr)
{
  let zeroIndex = -1;
  for(let i = 0; i < arr.length; i++)
  {
    let item = arr[i];
    if(item.toString() !== '0' && zeroIndex !== -1)
    {
      swap(arr, zeroIndex, i);
      zeroIndex++;
    }

    if(item.toString() === '0' && zeroIndex === -1)
    {
      zeroIndex = i;
    }
  }
}

Matt Ellen • Oct 7 '20 • Edited

OK, you beat me this time! :D You're about 3x faster

Swapping the toString()s for two comparisons speeds it up a bit, but it still takes more than double the amount of time yours does.

Removing the call to swap (but still swapping) makes them pretty much identical. I had no idea a function call could be so heavy.

Matt Ellen • Oct 7 '20

function put0AtTheBack(arr)
{
  let zeroIndex = -1;
  for(let i = 0; i < arr.length; i++)
  {
    let item = arr[i];
    if(item !== '0' && item !== 0 && zeroIndex !== -1)
    {
        let tmp = arr[i];
        arr[i] = arr[zeroIndex];
        arr[zeroIndex] = tmp;
        zeroIndex++;
    }

    if((item === '0' || item === 0) && zeroIndex === -1)
    {
        zeroIndex = i;
    }
  }
}

AlbertoM • Oct 7 '20

That's an interesting find, I also wasn't aware that a function call would have made it that much worse.

Matt Ellen • Oct 8 '20

Well, to be fair, that's over 100000 iterations. But surprising none-the-less.