loading...
Cover image for Not an "Easy" Algorithm: Rotating an Array, Three Ways

Not an "Easy" Algorithm: Rotating an Array, Three Ways

alisabaj profile image Alisa Bajramovic ・11 min read

Today's algorithm is the Rotate Array problem:

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

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem. Could you do it in place with O(1) extra space?.

For example, if you were given the array [1, 2, 3, 4, 5], and told to rotate it 2 steps to the right, the output should be [4, 5, 1, 2, 3]. After 1 step, the array would be [5, 1, 2, 3, 4], so that after 2 steps it would be [4, 5, 1, 2, 3].

On Leetcode, this problem is labeled "easy"--how they determine difficulty level, I'm not sure. However, I think this problem is by no means an "easy" one. There are many ways to solve this problem, which is part of why I like it, and I think each solution is complicated in its own way.

In this blog post, I'll walk through three different ways to approach and solve this problem: (1) popping and unshifting the elements in the array, (2) creating a new array where the elements start out shifted, and (3) reversing different sections of the array.

Approach #1: Popping and Unshifting

When working with arrays, a few methods come up all the time. One of which is .pop(), which "removes the last element from an array and returns that element" (you can read more about .pop() here). For example:

const arr = [1, 2, 3]
arr.pop() // would return 3
console.log(arr) // would return [1, 2]

Another common method used on arrays is .unshift(). This method "adds one or more elements to the beginning of an array and returns the new length of the array" (you can read more about .unshift() here). For example:

const arr = [2, 3]
arr.unshift(1) // would return 3, the new length of the array
console.log(arr) // would return [1, 2, 3]

Rotating an array right can also be thought of as moving the elements from the back of the array to the front of the array. In this problem, we want to move elements from the back of the array to the front, doing so k times. In a for loop, which will run k times, we can pop the last number off the back of the array, and unshift that number to the front of the array.

For example, let's say we were given the array nums = [1, 2, 3, 4, 5], and k = 2, so we should rotate the array 2 times. Using pop and unshift, we'd start by popping off the last element, 5, which would make nums be [1, 2, 3, 4]. Then, we'd unshift 5, putting it at the front of the array, so that nums is [5, 1, 2, 3, 4].

First line: `nums` on the left, and to the right is a series of blocks for `[1, 2, 3, 4, 5]`. Second line: `nums.pop()` on the left, and `5` in a blue block on its own. Third line: `nums` on the left, and to the right is a series of blocks for `[1, 2, 3, 4]`. Fourth line: `nums.unshift(5)` on the left, and on the right is a series of blocks for `[5, 1, 2, 3, 4]`, and the `5` is blue.

We'd repeat this cycle once more, popping off the 4, making nums = [5, 1, 2, 3], and then unshifting the 4, giving us the final answer of [4, 5, 1, 2, 3].

First line: `nums.pop()` on the left, and to the right is `4` in a blue block on its own. Second line: `nums` on the left, and to the right is a series of blocks for `[5, 1, 2, 3]`. Third line: `nums.unshift(4)` on the left, and on the right is a series of blocks for `[4, 5, 1, 2, 3]`, and the `4` is blue.

Coding the first approach

Before we start coding this solution, there's one more thing to note about this problem: let's say that the given array was [1, 2], and we were told to rotate it to the right 7 times. The array is less than 7 elements long, so rotating it 7 times would be a lot of unnecessary work. Therefore, before we do anything, both in this solution and in the other approaches, we should modify k using modulo (%).

The modulo operator returns the remainder after dividing one number by another. For example, 10%3 would return 1, because 10/3 has a remainder of 1. Similarly, in this problem, we'd want to set k equal to k % nums.length. Using the same example, if k = 7, and nums = [1, 2], then k = k % nums.length is the same as k = 7%2, or k=1. The first line of this solution, therefore, will be this line.

function rotate1(nums, k) {
  k = k % nums.length;
  //...
}

We want to do .pop() and .unshift() as many times as k equals, so we'll make a for loop that goes on k times. Inside the for loop, we'll store the result of nums.pop() to a variable called back. Then, we will unshift back, putting in at the start of the nums array.

Once the for loop stops executing, we'll return nums.

function rotate1(nums, k) {
  k = k % nums.length;
  for (let i = 0; i < k; i++) {
    const back = nums.pop();
    nums.unshift(back);
  }
  return nums;
}

This first approach is done in linear time (O(n)) and constant space (O(1)).

Approach #2: Creating a New Array

In the second approach, we'll be creating a new array, where the elements have moved over k spaces. The idea behind this approach is that we can just iterate through the nums array, and move each element k spaces to the right of where it already was.

What happens if the element is supposed to move to a index that's longer than the length of the nums array? In that case, you'd want to use the modulo operator, calculating the result of moving to the new distance % the length of the nums array. I think this is a particularly tricky part of this approach, so I'll use an example.

Let's say you're starting out with the array nums, which is [1, 2, 3] and a blank array arr, and we're told k=2, so the array will move over 2 spots to the right. We can start out by moving the first element of the nums array, 1. 1 is at index 0 (i = 0), and we'll want to move it 2 spots over. In other words, we'll want its position in the arr array to be determined by i + k, which is index 2.

First row: `nums` on the left, and a series of blocks for `[1, 2, 3]` on the right. Second row: `arr` on the left, and an empty block representing an empty array on the right. Third row: `i = 0; i + k = 2` on the left, and a blue block for `1` on the right. Fourth row: `arr` on the left, and a block with two blank spaces, followed by a blue `1` on the right (representing an array `[<empty>, <empty>, 1]`).

Now, we're on index 1 of the nums array, 2. We want to move it k steps to the right, but i + k is 3, and that would be longer than the length of the nums array. So, to find the new spot for 2, we should do (i + k) % nums.length, or 3 % 3, which is 0. So, we should move the element 2 to the index 0 in arr.

First row: `i = 1; i + k = 3; nums.length = 3; 3%3 = 0` on the left, and a blue block for `2` on the right. Second row: `arr` on the left, and a block with the first space as a blue box with `2`, second box is blank, and third box is `1`, on the right (representing an array `[2, <empty>, 1]`).

Finally, we're on the index 2 of the nums array, which is 3. We want to move it k steps to the right, and i + k is 4, which is longer than the length of the nums array. So, to find the new spot for 3, we should do (i + k) % nums.length, or 4 % 3, which is 1. So, we should move the element 3 to the index 1 in arr, giving us the final result of this problem.

First row: `i = 2; i + k = 4; nums.length = 3; 4%3 = 1` on the left, and a blue block for `3` on the right. Second row: `arr` on the left, and a block with the first space as `2`, second space is a blue box `3`, and third box is `1`, on the right (representing an array `[2, 3, 1]`).

Coding the second approach

To start out this solution, we'll do the same modifications to k that we did in the first approach. We'll then initialize a new, empty array called arr.

function rotate2(nums, k) {
  k = k % nums.length;
  let arr = [];
  //...
}

Now, we'll use a for loop to go through every element in nums. At each index, we'll place that element in the new spot in arr. We can find that new spot by doing (i + k) % nums.length. So, we'll set arr[(i + k) % nums.length] equal to nums[i].

function rotate2(nums, k) {
  k = k % nums.length;
  let arr = [];
  for (let i = 0; i < nums.length; i++) {
    arr[(i + k) % nums.length] = nums[i];
  }
  //...
}

Now, arr will be the rotated array that we want. However, in this problem, we should be modifying the nums array, so we have to set each index in nums equal to the value at that index in arr. To do this, we can set up another for loop. At each index, we'll set nums[i] equal to arr[i]. When the for loop ends, we can return nums.

function rotate2(nums, k) {
  k = k % nums.length;
  let arr = [];
  for (let i = 0; i < nums.length; i++) {
    arr[(i + k) % nums.length] = nums[i];
  }
  for (let i = 0; i < nums.length; i++) {
    nums[i] = arr[i];
  }
  return nums;
}

This second approach is done in linear time (O(n)) and linear space (O(n)).

Approach #3: Reversing the Sections

In this third approach, we're going to be reversing parts of the nums array three times. The first time, we'll reverse the entire array. The second time, we'll reverse the first k elements of the array. The third time, we'll reverse the final elements of the array, from k to the end.

The idea behind this approach can best be seen with an example. We'll start with the array [1, 2, 3, 4, 5], and we're going to want to rotate it 2 steps. We'll start by rotating the entire array.

Two arrays represented as a two blocks, with a red array going from the left to right. The entire array on the left has a blue border and is filled with white, and is `[1, 2, 3, 4, 5]`. The array on the right has a black border and is filled with blue, and is `[5, 4, 3, 2, 1]`.

Now, we'll want to rotate the first k elements. Since k is 2, we'll rotate the elements at 0 and 1.

Two arrays represented as a two blocks, with a red array going from the left to right. The first two elements in the array on the left have a blue border and are filled with white. The last three elements have a black border and are filled with white. The array on the left is `[5, 4, 3, 2, 1]`. The array on the right has the first two elements filled with blue with a black border. The last three elements are filled with white with a black border. The array is `[4, 5, 3, 2, 1]`.

Finally, we'll rotate the last elements, from index k to the end. This gives us the final array that we want.

Two arrays represented as a two blocks, with a red array going from the left to right. The last three elements in the array on the left have a blue border and are filled with white. The first two elements have a black border and are filled with white. The array on the left is `[4, 5, 3, 2, 1]`. The array on the right has the first two elements filled with white and have a black border. The last three elements have a black border and are filled with blue. The array is `[4, 5, 1, 2, 3]`.

Coding the third approach

To code this solution, we'll write a function called reverse within the rotate function, and we'll call it three times. To start, however, we'll do the same modification to k that we did in the previous two approaches.

function rotate3(nums, k) {
  k = k % nums.length;
  //...
}

Then, we'll call the function reverse (which we'll write in a minute), and we'll call it three times. reverse() will take in the array, the index to start reversing, and the index to end reversing. So, the first call to reverse() will pass in nums, 0 (as the start index), and nums.length-1 (as the end index). The second call to reverse() will pass in nums, 0 (as the start index), and k-1 (as the end index). The third call to reverse() will pass in nums, k (as the start index), and nums.length-1 (as the end index).

function rotate3(nums, k) {
  k = k % nums.length;
  reverse(nums, 0, nums.length - 1);
  reverse(nums, 0, k - 1);
  reverse(nums, k, nums.length - 1);
  //...
}

Now, we can write the function reverse, whose parameters will be nums, start, and end. In this function, we'll switch the values at the start and end index, and will move start and end toward the center. We'll keep doing this as long as start is less than end.

So, we'll write a while loop, that will keep going as long as start is less than end. Inside the loop, we'll keep a temporary variable that will store the value of the nums array at the start index. Then, we'll set the value at the start index equal to the value at the end index, and the value at the end index equal to the temporary variable. We'll move start toward the middle by incrementing it, and we'll move the end toward the middle by decrementing it. Finally, when the while loop is done executing, we'll return nums to the rotate function.

function rotate3(nums, k) {
  k = k % nums.length;
  reverse(nums, 0, nums.length - 1);
  reverse(nums, 0, k - 1);
  reverse(nums, k, nums.length - 1);
  //...

  function reverse(nums, start, end) {
    while (start < end) {
      let temporary = nums[start];
      nums[start] = nums[end];
      nums[end] = temporary;
      start++;
      end--;
    }
    return nums;
  }
}

Once each reverse() function is done executing, the final thing to do will be to return nums.

function rotate3(nums, k) {
  k = k % nums.length;
  reverse(nums, 0, nums.length - 1);
  reverse(nums, 0, k - 1);
  reverse(nums, k, nums.length - 1);
  return nums;

  function reverse(nums, start, end) {
    while (start < end) {
      let temporary = nums[start];
      nums[start] = nums[end];
      nums[end] = temporary;
      start++;
      end--;
    }
    return nums;
  }
}

This solution is done in linear time (O(n)) and constant space (O(1)).

--
Let me know in the comments if you have any questions or ideas for other ways to solve this!

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

pic
Editor guide
 

After reading the problem, just on top of my head, this can be easily solved with a ring buffer. Best of all, it can be implemented in any language.

 

Quick and really dirty and not exactly efficient :D

function rrotate(arr, steps) {
  steps = (steps || 0) % arr.length;
  return new Proxy(arr, {
    get(target, prop) {
      const idx = typeof prop === "string" ? Number(prop) - steps : NaN;
      return Number.isInteger(idx) ?
         target[idx >= 0 ? idx : target.length + idx] :
         target[prop];
    }
   });
}

But it works (mostly)

Array.from(rrotate([1,2,3,4,5], 2))
// [4, 5, 1, 2, 3]
rrotate([1,2,3,4,5], 2).slice()
// [4, 5, 1, 2, 3]
rrotate([1,2,3,4,5], 2).forEach(e => console.log(e))
// 4
// 5
// 1
// 2
// 3
[...rrotate([1,2,3,4,5], 7)]
// [4, 5, 1, 2, 3]
for (let e of rrotate([1,2,3,4,5], 12)) console.log(e);
// 4
// 5
// 1
// 2
// 3
 

A good point, one of those if you knew the actual problem you'd find a way of solving it better than actually manipulating an array which feels "expensive".

 

I feel exactly there opposite on this. Using built in methods to manipulate an array (slice in my case) feels less expensive to me because I expect the engineers working on the browser build optimizations into their implementations of these methods.
Not looking to argue it just throwing another perspective in there.

I guess my point was that the array is a specific data structure, I expect it to be optimised for being an array. If my problem is something that includes a "rotation" then a rolling buffer may well be a better algorithm - requires no shifting, just a very slightly more complicated retrieve operation and then move a head and tail pointer.

For example: if you are constantly inserting all over a list and only rarely retrieving all the items then no contiguous array, no matter how optimised, will be anywhere near the performance of a linked list.

If I want to implement a thing that has the last 100 values in it then shifting an array for every insertion is massively more costly than increment and modulus. Getting a new array with slice is allocating memory every time. It's easy to write the code, but the consequences may be significant under load.

Totally agree with your linked list example, and your argument about multiple shifts getting expensive quickly.
I am curious though, do you think creating a new data structure from the original array is going to use less memory than the slice solution? Probably would have to dig into the source to be sure, but curious about your intuition here.

It's probably the game programmer in me coming out. Don't allocate things because something has to garbage collect them later. That takes time, causes glitches etc.

I wrote the below a while ago about this. It really doesn't matter if you are sure the code isn't going to work on giant data or be called frequently. If that is the case then my "dont allocate/copy/garbage collect" OCD kicks in :)

Nice article. It's actually something I've given little though to. Thanks for sharing, I'm sure I'll think of it in the future now.

Glad you like it :) Honestly only do that when it matters though - I mean I write code that uses all of the slow things when I know it will not be handling lots of data because it's quicker to write and that is the important thing for the task at hand!

Specifically on your point of immutability, a lot of frameworks in many languages implement collections like this. I usually just use them without even thinking about the memory issues. Your example in the article is very eye opening!

Yeah immer.js allows you to mutate arrays and then it works out an immutable version from it. That's very cool, but still has a cost as I replied in the comments to that article with a sandbox example showing (on my machine at least) significant frame drops in some use cases.

It so happened the example I had given and then implemented in immer is a kind of kryptonite to immer.js (because it happens over multiple cycles) but yeah, I see things on DEV all the time that use spread in loops - I just think, hope no one calls that example with 1 million entries not the example 10!

 

Nice write up. Thanks for sharing.

Another solution could use slice along with the spread operator:

function rotate(array, num) {
  const size = array.length;

  if(num === 0 || num === size) {
    return array;   
  }

  if(num < 0) {
    num = size + num;
  }

  if(num > size) {
     num = num - size;
  }

  return [
    ...array.slice((num * -1), size),
    ...array.slice(0, size - num)
  ];
}
 

Hi,
I followed this article and thank you for doing it.
Can I ask you how did you think about them?
I mean, you have used some particular pseudocode or resource?
You know what a pleasure to solve these problems , but make a huge effort yet.
P.S Sorry for my bad English

 

I would have though the shortest version of (1) would be:

    let rotate = (arr,n) => (arr.unshift(...arr.splice(-n % arr.length, n % arr.length)), arr)

Though I guess the splice allocates an array of size n % length

 

There's also the reference implementation for C++'s rotate() method

It has the ability to rotate a smaller sub-section of an array as well. The array that started as [array[0], ... array[first], array[first+1], ..., array[middle], array[middle + 1], .... array[last -1] (array[last], which might be the magical just off the edge n+1th item), ...]
will become [array[0], ... array[middle], array[middle+1], ..., array[last -1], array[first], array[first + 1], .... (array[last], which is the first index that does not move), ...]

C++ has some non-javascriptisms, so let's a js transliteration:

function rotate (array, first, middle, last)
{
  next = middle;
  while (first!=next)
  {
    swap (array, first++, next++);
    if (next==last) next=middle;
    else if (first==middle) middle=next;
  }
}

// A well-known C++ library function. Simple implementation here.
function swap(arr, i, j){
  temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
 

Nice post! I have two solutions, neither of which is better than yours, but still might be interesting.

Approach 1: Functional style, easy to read but slow

const head = (arr, k) => arr.slice(0, k);
const tail = (arr, k) => arr.slice(k);
const rotator = (arr, k) => [...tail(arr, k), ...head(arr, k)];

Approach 2: using recursion and modifying the array in place

const recursed = (arr, k) => k == 0 ? arr : (arr.push(arr.shift()) , recursed(arr, --k)); 
 

Nice approach, just wanted to point out the typo, in the 3rd approach it says coding the second approach and in the following paragraph instead of num.0 it is num,0.

 

I never thought of using modulo. Nice post!