Algorithms 101: Rotate Array in JavaScript — three solutions

Noob v. Algorithms #22, playing with .pop(), .unshift() and .splice()

Joan Indiana Lyness
Nov 18 · 5 min read
rotate right!

Browsing through the top interview questions in LeetCode, one of the harder easy questions is this one:

First solution: while loop using .pop() and .unshift()

The easiest solution is to use JavaScript’s .pop(), which destructively removes and returns the last element of the array (MDN documentation here), in combination with .unshift(), which destructively adds elements to the start of the array (MDN documentation here).

Here’s how that works:

In this challenge, we want to perform the operation k times. We could do it by setting up a while loop:

Let’s unpack that.

On line 2, we’re setting a counter with an initial value of zero. At the end of each loop (on line 5), we increment the counter by one.

On line 3, we’re saying: “while our counter is less than the number of times we’re supposed to perform the loop, go ahead and loop”.

Note: yes, i started the counter at zero, instead of one. If you want to start yours at 1, then in line 3, write while i <= k instead of while i < k.

This works, but is not that fast:

How can we speed this up? I decided to try .splice() instead of .pop()

Second Solution: .splice() instead of .pop()

LeetCode performance times are not very consistent. When I first tried this solution, .splice() ran faster than .pop(); later it seemed the same.

When you remove an item from an array, the items after that have to move forward to take the missing item’s place in memory. Depending on how big the array is, this can slow down run-time. (Since all of an array’s elements must be ‘seated together’ in memory, the elements must be re-indexed every time the array is altered).

If you are always removing the last item in the array, there are no later items, so you can skip the re-indexing. By definition .pop() always removes only the last item. So it’s fast at what it does.

.splice() can target items anywhere in the array; so when it targets anything but the last item, it is slower.

.splice() takes two arguments.

  • the index at which you want to start removing items. (Use -1, -2, to indicate last, second-to-last etc . indices of the array.)

It is a destructive method that alters the original array. (If you want a non-destructive method, try .slice(), which takes different arguments. Here is MDN documentation on .splice() and .slice() ).

Here’s how .splice() works:

In our challenge, we can use it like so:

but … (sigh) … it ain’t faster:

Third solution: optimize for different scenarios.

So far, our code approaches by popping off one element at a time and appending it to the front of the array. It works the same way whether we have a short or long array; and whether we are supposed to pop off 1 item or 1 million items.

We can speed things up by optimizing for different scenarios. What if we have an array of 100 elements, and k is 90? If we pop off last item and append it to the front of the array 90 times, we have to re-index the array …. 90 times. That’s a lot.

How about if we just splice() off the last k items from the end, and add them to the front of the array as one block?

We could do that like so:

Notice:

  • we are using -k to .splice() off the last k items of the array.

Running the code as is:

whoops ….

does not work …

because it misses edge cases where the number of times we need to rotate, k, is greater than the array’s length.

To handle the edge cases, we can add an if /else statement:

Notice that the else statement uses the code from our second solution!

And now our code runs way faster:

You can see the code execute live here, on PythonTutor.com

and you can play with it here on repl.it:

https://repl.it/@Joan_IndianaInd/rotate-arrays-leetcode

Copyright © Joan Indiana Lyness 2019

Next: Algorithms 101 #22, Difference between Two Arrays in JavaScript

In case you missed it: Algorithms 101, #20, .includes() vs. indexOf() in JavaScript

JavaScript in Plain English

Learn the web's most important programming language.

Joan Indiana Lyness

Written by

Hire me in Washington DC! Full-stack developer, Ruby, Rails, JavaScript, i love! React. My portfolio: https://joan-indiana-lyness.com/projects

JavaScript in Plain English

Learn the web's most important programming language.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade