A cassidoo newsletter question

If you’re a web developer, and you don’t know who cassidoo is, let’s fix that. Check out her Twitter. I’ve subscribed to her newsletter, which is chocked full of tidbits, musings, and a question every week. I thought it would be pretty cool to actually share how to work through the problem set.

Problem Set

Given an integer array, move all 0s to the end of it while maintaining the relative order of the non-zeroes.

Example

$ moveZeroes([0,2,0,3,8])
$ [2,3,8,0,0]

The process

I’ll be working out the problem using JavaScript. First, we need to declare the function and return an array. The question has a bonus request to return the same array and not a copy, so I’ll be working with that approach in mind:

function moveZeroes(arr) {
  return arr;
}

Next, we’ll need to iterate over the array to determine whether or not the value is zero. I’ll take the index of where those zeros are located and store them in a new array:

function moveZeroes(arr) {
  let i = 0
  const indexOfZeros = []
  while (i < arr.length) {
    if (arr[i] == 0) {
      indexOfZeros.push(i)
    }
    ++i
  }

  return arr;
}

Now, I’ll need to splice zeros from the array. I reversed the array of the index of zeros because if I spliced the first zero, it would change the order index of the array during the iteration, which could accidentally skip another occurrence of zero if one were to follow right after another. Removing them in reverse guarantees I don’t disturb that order:

function moveZeros(arr) {
  let i = 0
  const indexOfZeros = []
  while (i < arr.length) {
    if (arr[i] == 0) {
      indexOfZeros.push(i)
    }
    ++i
  }
  indexOfZeros.reverse()

  indexOfZeros.forEach(function (value) {
    arr.splice([value], 1)
  })

  return arr
}

Lastly, each occurrence I remove a zero, I immediately add one using a push method on the array:

function moveZeros(arr) {
  let i = 0
  const indexOfZeros = []
  while (i < arr.length) {
    if (arr[i] == 0) {
      indexOfZeros.push(i)
    }
    ++i
  }
  indexOfZeros.reverse()

  indexOfZeros.forEach(function (value) {
    arr.splice([value], 1)
    arr.push(0)
  })

  return arr
}

Additional test cases

I decided to generate random arrays during each execution to confirm testing:

function moveZeros(arr) {
  let i = 0
  const indexOfZeros = []
  while (i < arr.length) {
    if (arr[i] == 0) {
      indexOfZeros.push(i)
    }
    ++i
  }
  indexOfZeros.reverse()

  indexOfZeros.forEach(function (value) {
    arr.splice([value], 1)
    arr.push(0)
  })

  return arr
}

let randomArray = Array.from({ length: 100 }, () =>
  Math.floor(Math.random() * 10)
)

console.log(randomArray)
console.log(moveZeros(randomArray))

Output:

[
   0, 3, 9, 3, 9, 9, 8, 6, 0, 0, 4, 6,
   6, 7, 4, 8, 4, 9, 5, 2, 3, 0, 4, 9,
   3, 8, 1, 8, 5, 2, 3, 7, 0, 4, 3, 0,
   6, 5, 7, 3, 2, 8, 9, 0, 2, 4, 1, 9,
   0, 6, 4, 4, 4, 8, 9, 1, 4, 0, 5, 9,
   8, 3, 3, 8, 6, 5, 9, 1, 2, 4, 9, 1,
   3, 5, 6, 4, 2, 4, 6, 3, 0, 8, 0, 7,
   5, 7, 6, 7, 9, 6, 3, 9, 2, 2, 1, 1,
   6, 7, 6, 8
 ]
 [
   3, 9, 3, 9, 9, 8, 6, 4, 6, 6, 7, 4,
   8, 4, 9, 5, 2, 3, 4, 9, 3, 8, 1, 8,
   5, 2, 3, 7, 4, 3, 6, 5, 7, 3, 2, 8,
   9, 2, 4, 1, 9, 6, 4, 4, 4, 8, 9, 1,
   4, 5, 9, 8, 3, 3, 8, 6, 5, 9, 1, 2,
   4, 9, 1, 3, 5, 6, 4, 2, 4, 6, 3, 8,
   7, 5, 7, 6, 7, 9, 6, 3, 9, 2, 2, 1,
   1, 6, 7, 6, 8, 0, 0, 0, 0, 0, 0, 0,
   0, 0, 0, 0
 ]

Conclusion

This problem set was really fun to work through. My initial approach to use JavaScript was a little challenging since I’ve been working with PHP lately. The MDN documentation helped a lot in understanding the differences between splicing and exploding methods which is what ultimately led me towards the correct solution. I’ve shared my code on GitHub if you want to take a look yourself.

Leave a Reply