Rotate an Array

If you've followed my blog for the last couple of years then you'll know that I've been training on CodeWars semi-frequently for a few years. Okay, maybe "semi-frequently" is a little generous and it's more like "I do this when it's been long enough that I feel a little guilty." But I have been at it for a while! While CodeWars challenges may not be for everyone, and they certainly don't give you the breadth of programming experience that you get from building, debugging, and deploying a real-world application, these coding problems are useful in drilling into the fundamentals of programming languages. Common solutions often rely on things like array or string methods or RegEx, and optimized solutions can expose you to less-commonly-used language features. This kind of study can deepen your understanding of what's possible with any particular programming language.

CodeWars obviously isn't the only website that does this. HackerRank is another, and so is LeetCode. LeetCode has come onto my radar pretty frequently in the last few months. People on Twitter who were also studying Algorithms and Data Structures and participating in the #100DaysOfCode Challenge cited LeetCode as a good place to learn about and challenge themselves on those topics. It also looks like LeetCode is a platform that some companies use in their recruitment and hiring process for coding challenges. This all made me feel like I needed to give it a shot and gain a little bit of familiarity with the platform.

Today I want to write about a problem that LeetCode gave me, that from the looks of it comes up fairly regularly in interviews. This problem is called Rotate an Array, and it gave me a fair amount of trouble. I had a few solutions that almost worked, and one solution that did work but took way too much time. I'll walk through what those were, as well as a better solution that wasn't readily apparent to me.

Prompt

Given an array, nums, rotate the array to the right by k steps, where k is non-negative.

Example 1

Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 3

Output: [5, 6, 7, 1, 2, 3, 4]

Explanation:

rotate 1 steps to the right: [7, 1, 2, 3, 4, 5, 6]rotate 2 steps to the right: [6, 7, 1, 2, 3, 4, 5]rotate 3 steps to the right: [5, 6, 7, 1, 2, 3, 4]

Example 2

Input: nums = [-1, -100, 3, 99], k = 2

Output: [3, 99, -1, -100]

Explanation:

rotate 1 steps to the right: [99, -1, -100, 3]rotate 2 steps to the right: [3, 99, -1, -100]

It seems simple, right? I thought so too, but once I dove in I realized it wasn't as easy as it first appeared.

First Solution: Splicing and Spreading

The first way I thought to tackle this problem was by using the .splice() array method and Array Spread. Let's take a look at the code.

function rotate(nums, k) {  const spliced = nums.splice(nums.length - k, k);  return [...spliced, ...nums];}

Now this does work, to a certain extent, and I like it because it's nice and clean. The .splice() method cuts k items out from end of the array and stores them into a variable named spliced. We then spread spliced's contents into a new array, followed by what's left of nums's contents. This new array then gets returned.

If you run rotate([1, 2, 3, 4, 5, 6, 7], 3), the spliced variable would be [5, 6, 7], and the remainder of nums would be [1, 2, 3, 4]. Spreading these two values together would then give you [5, 6, 7, 1, 2, 3, 4].

The problem with this solution shows up if the value of k is greater than twice the length of nums. At that point, nums.length - k calculates to -k or lower, and .splice() doesn't know what to do. Let's take a look at this with a simpler example.

function rotate(nums, k) {  const spliced = nums.splice(nums.length - k, k);  return [...spliced, ...nums];}
console.log(rotate([1, 2], 0));// result: [1, 2]console.log(rotate([1, 2], 1));// result: [2, 1]console.log(rotate([1, 2], 2));// result: [1, 2]console.log(rotate([1, 2], 3));// result: [2, 1]console.log(rotate([1, 2], 4));// result: [1, 2]console.log(rotate([1, 2], 5));// result should be [2, 1]// actual result is [1, 2] Uh oh!!console.log(rotate([1, 2], 6));// result: [1, 2]console.log(rotate([1, 2], 7));// result: [1, 2] -- it's [1, 2] from here onward

If you run the above code you'll see that once k is 5, or any value greater than twice the length of the array, the .splice() operation fails, and regardless of the value of k, the array is returned in its original order. I'm not totally certain about why this happens when it does. I know that .splice() does work with negative numbers, but I think in this case, the failure results from having such a big gap between the negative value we tell .splice() to start with, and k, the value we tell .splice() to end on.

At any rate, we want to be able to pass in any positive integer value to k and still get a properly rotated array. This edge case proves that this solution will not work.

Second Solution: Looping

The next approach I tried out was a brute force loop through the array. I would run through the array k times, and for each iteration, I would perform a .pop() method, which removes the last item from the array, and then .unshift() that value, which places that value at the beginning of the array.

function rotate(nums, k) {  for (let i = 0; i < k; i += 1) {    nums.unshift(nums.pop());  }  return nums;}

This solution is a little bit longer than the previous one, but I think it's fairly straight-forward. If we run rotate([1, 2, 3, 4, 5, 6, 7], 3) then our loop runs three times.

On the first iteration, we .pop() the value of 7 off of the end, and then .unshift() it to the beginning of the array.

[1, 2, 3, 4, 5, 6, 7] => [7, 1, 2, 3, 4, 5, 6]

On the second iteration, we .pop() and .unshift() 6.

[7, 1, 2, 3, 4, 5, 6] => [6, 7, 1, 2, 3, 4, 5]

On the final iteration, we .pop() and .unshift() 5.

[6, 7, 1, 2, 3, 4, 5] => [5, 6, 7, 1, 2, 3, 4]

This works, but the problem is that it's very time-intensive. To begin with, we're looping through the array k number of times. If k is greater than or equal to the length of the array, then we're starting off at O(n) time. But furthermore, each time we do the .pop() and .unshift() operations, we're moving an item to the front of the array, and every single item after that needs to be re-indexed. I believe that this brings us up to O(n * k), if not something that performs even worse than that.

What we need is a good way to eliminate as much of the re-indexing as possible while swapping numbers in place within the array, which leads us to the third solution, which is the one I wound up submitting.

Third and Submitted Solution: Reversing

I'll admit that I looked this solution up. I had already spent probably 45 minutes arriving at the above solutions and hitting the walls of their edge cases and performance issues. Doing these coding challenges can be like that. It can be frustrating and time-consuming and sometimes you just cannot figure out the answer on your own. But remember that it's in moments where you're pushing yourself beyond your boundaries that you're learning the most, even if it feels like you're up against the limitations of your knowledge.

When I was in my coding bootcamp, my instructor told me that it's good to try problems like these out on your own, but if after about 45 minutes you can't come up with the answer then it's perfectly fine to ask or look for help.

I'm glad that I did, because I would have never landed on this solution on my own. Let's take a look at the code and then break down what it does and why it works so much faster than the previous solution.

function rotate(nums, k) {  function reverse(arr, start, end) {    while (start < end) {      [arr[start], arr[end]] = [arr[end], arr[start]];      start++;      end--;    }  }
  k %= nums.length;  reverse(nums, 0, nums.length - 1);  reverse(nums, 0, k - 1);  reverse(nums, k, nums.length - 1);  return nums;}

The foundational thing that needs to happen when rotating the array is that the elements at the end of the array need to be brought up to the beginning of the array, sending the values that were previously at the beginning of the array to the end.

This solution embraces that from the get-go, and the first thing it does is reverses the entire array. Then it finds the k number of values at the start of the newly reversed array, and reverses those values. After that, it then reverses the remaining values from k to the end. If we run rotate([1, 2, 3, 4, 5, 6, 7], 3), then these three operations look like this:

Step 1: Reverse The Entire Array

[1, 2, 3, 4, 5, 6, 7] => [7, 6, 5, 4, 3, 2, 1]

Step 2: Reverse the First k Values

[7, 6, 5, 4, 3, 2, 1] => [5, 6, 7, 4, 3, 2, 1]

Step 3: Reverse the Rest of the Values

[5, 6, 7, 4, 3, 2, 1] => [5, 6, 7, 1, 2, 3, 4]

We accomplish the above by using a helper function called reverse, which takes an array and two indexes. The first index is the beginning location of the values we want to reverse, and the second index is the ending location of those values.

The first reverse() function call is easy, we just pass the beginning of the array (index 0) and the end of the array (index nums.length - 1).

The second reverse() call is for the first k elements, so we pass the beginning of the array (index 0) as the first index, and k - 1 as the second index.

The third reverse() call just runs on the remainder of the array, so we pass it k as its first index, and nums.length - 1 for the end of the array.

I also want to call attention to the following statement: k %= nums.length. This line helps us to address one of the issues we faced above, when k is a value that's larger than the length of the array. Think about it like this: if an array has two items, and k is 3, rotating it 3 times results in the same thing as rotating it 1 time. If nums has 4 items, and k is 6, rotating it 6 times results in the same thing as rotating it 2 times. The k %= nums.length - 1 helps us reduce k down to the smallest number of steps that we need to take, and if k is larger than the number of array items, then this statement just calculates the remainder above the number of items in the array.

It's clever! And clearly not what I thought of at first. But by going this route, we reach a constant time complexity O(n), since the array elements are always reversed a total of 3 times. And more importantly it taught me a new way to step back and think about this problem.

The nice thing about CodeWars and LeetCode challenges is that there's almost always more than one viable solution. A well-written challenge will have tests that draw out the edge case limitations of your solution, forcing you to reevaluate. That can be very frustrating when you've spent so much time coming up with a solution that seemed to work with the initial test cases, but that process of reevaluating and (after 45 minutes or so of hitting brick walls) looking for a better solution.

That space just beyond the edges of your limitations is where the most effective growth and learning can happen, even if it often comes with feelings of frustration. When you do finally have to look for a solution, slow down and read through the solution line by line to really understand how it works and why it may be a better option than the ones you came up with.