CoDEVIANT #18 (10/5/20) — Sprinkles on Top!

Once upon a time, I had a really wild dream. I dreamt that I was in the last ice-cream shop in the galaxy; it was right on the edge of the cosmos. In most diner-style ice-creameries, you can peruse a juke-box containing myriad more choices of songs than there are flavors behind the counter. In my dream, however, it was quite the opposite. The taste combinations were everything you ever wanted, even if — in some cases — you had never conceived of them before. The aliens working the joint were friendly and passionate about frozen dairy dessert products, but conveyed a lack of nuance with regards to how to assort toppings on top of the generous scoops. In my dream, I somehow became a fellow employee and was sharing the concept of applying sprinkles, cherries, syrups, and molten fudge to the top of these confections.

I actually didn’t have this dream, but I have a sweet-tooth and someone told me I was good at writing, so I wanted to in indulge in creative writing for a second. Today’s problem, however, reminded me of this dream I made up.

Problem: We get an array of integers and an integer. We want to write a function that moves all instances of the latter integer to the end of the array. That’s it.

So what does this have to do with ice-cream? Well in my crazy-head, I imagine it like having a bowl (our array) with scoops of ice-cream (the other elements that don’t match our target integer) and pieces of a particular topping (our target integer when it pops up). Our job is to assemble an ice-cream cone with all of our toppings at the end.

We want our whipped-cream integer-elements at the end of the array. Doesn’t that look good? I mean it’s diabetes on a cone, but DAYUM.

So I was a super nerd and came up with not one, but TWO solutions.

Adrian’s Solution 1:

function moveElementToEnd(array, toMove) {
 let arr = []
 arr = array.filter(el => {
  if(el !== toMove) {
  return el
  }
 })
let counter = array.length - arr.length
for(let i = 0; i < counter; i++) {
  arr.push(toMove)
}
 return arr
}

We start off creating a new element called arr which is an empty array.

let arr = []

Then we make arr equal the result of the filter method being used on our array argument that is passed in. The filter rule is that if the element being iterated over DOES NOT equal our target integer (i.e. our sprinkles/whipped-cream number), then arr will have the element pushed into it.

let arr = []
arr = array.filter(el => {
  if(el !== toMove) {
     return el
  }
})

Next, we create a variable called counter and make it equal to the difference between the length of array and arr.

let counter = array.length - arr.length

Then I create a classic for-loop where I keep the loop active as long as i stays lower than counter. In the block of the loop, I push our target integer (sprinkles/whipped-cream number) to the end of arr. Then I return arr.

for(let i = 0; i < counter; i++) {
  arr.push(toMove)
}
return arr

So that was the first one. And it was cool and all except that I used two for-loops, when I probably could’ve solved it with one. Depending on the length of the array we get, this could be taxing on the computer. I believe the Big O Notation for this solution would be O(2N) which would be Linear Time (but doubled)…I think

If anyone could correct me on that, that’d be cool.

Adrian’s Solution 2:

I sought to make something that was leaner and would be more light-weight on the computer and I think I did a pretty good job.

function moveElementToEnd(array, toMove) {
 let soughtValues = []
 let otherValues = []
 array.forEach(el => {
  if(el === toMove) {
   soughtValues.push(el)
  } else {
   otherValues.push(el)
  }
 })
 return otherValues.concat(soughtValues)
}

I create two variables that are empty arrays: soughtValues and otherValues.

let soughtValues = []
let otherValues = []

Then I use the forEach method on the array that is passed in. In the method’s block, I tell the computer to push the element being iterated over into the soughtValues array if it matches the target/sprinkles integer. In every other case, I have the other numbers pushed into the otherValues array.

array.forEach(el => {
  if(el === toMove) {
   soughtValues.push(el)
  } else {
   otherValues.push(el)
  }
 })

Then I return the otherValues array with the concat method chained on it with the argument of the soughtValues array.

return otherValues.concat(soughtValues)

Essentially this returns an array that equals otherValues with the values of soughtValues tacked on at the end. And so we get our perfect ice-cream cone.

Now let’s see how the real ice-creamery pros did it (and by that I mean the super nerds)

function moveElementToEnd(array, toMove) {
 let a = 0
 let z = array.length - 1
 
 while(a < z) {
  while(a < z && array[z] === toMove) {
   z --
  }
  
  if(array[a] === toMove) {
   array[a] = array[z]
   array[z] = toMove
  }
  
  a++
 }
 return array
}

So what’s cool about this solution is that it swaps out the values of the array elements in-place meaning that it doesn’t require the creation of any new data-structure (empty arrays). Basically it is putting a pointer at the end and start of the array we are given. While the first pointer, a, is a lesser value than the end pointer, z, some code runs.

let a = 0
let z = array.length - 1

In this code, we create an inner while-loop that says that (again because JavaScript can be funny) if the first pointer (a) is less than the end-pointer (z) AND if array[end-pointer (z)] equals our sprinkles value, we decrement the end-pointer, z, by one until array[z] does not equal our sprinkles value.

while(a < z) {
   while(a < z && array[z] === toMove) {
      z--
   }
   ...
}

Then inside of the outer while-loop we create an if-statement saying that “if the value at array[a] equals our sprinkle value, we make array[a] equal whatever array[z] is at that time (as it could not possible be our sprinkle value) and then we make array[z] equal our sprinkle value.

while(a < z) {
   while(a < z && array[z] === toMove) {
      z--
   }
   if(array[a] === toMove) {
      array[a] = array[z]
      array[z] = toMove
   }
}

Then we increment a by one, outside of the if statement but still within the scope of the outer while-statement.

while(a < z) {
   while(a < z && array[z] === toMove) {
      z--
   }
   if(array[a] === toMove) {
      array[a] = array[z]
      array[z] = toMove
   }
   a++
}

Then, outside of any while-loop, we return the array!

function moveElementToEnd(array, toMove) {
 let a = 0
 let z = array.length - 1
 
 while(a < z) {
  while(a < z && array[z] === toMove) {
   z --
  }
  
  if(array[a] === toMove) {
   array[a] = array[z]
   array[z] = toMove
  }
  
  a++
 }
 return array
}

This, because it has a time-complexity of O(n) Linear Time (because we didn’t have to do any excess looping) and a constant space-complexity of O(1) (because we didn’t have to create new data-structures) is a much sweeter deal.

Pretty delicious, no? Thanks for geeking out with me and if you don’t mind, I’m going to get myself a bowl of chocolate-chip mint.

Ciao!