Cyclic Rotation of Array Elements

While the DSA 450 problem only asks you to rotate the array cyclically by one, we will go a step beyond the required and discuss how to cyclically rotate k positions of an array. Let's start with cyclically rotating the array by one.

Rotate One Element

Here is what we are asked in this problem

// input array
[1, 2, 3, 4, 5]
// output array
[5, 1, 2, 3, 4] // the last element gets to the front

I would recommend you try to code this one on your own. If you get stuck somewhere refer to the code below:

function cyc_rotate(arr) {
  let n = arr.length;
  let temp = arr[n - 1];
  for (let i = n - 1; i > 0; i--) {
    arr[i] = arr[i - 1];
  }

  arr[0] = temp;
  return arr;
}

console.log(cyc_rotate([1, 2, 3, 4, 5]))
-> [ 5, 1, 2, 3, 4 ]

If you were able to pull that on off GG! If not, don't worry just try to wrap your mind around indexes and elements of an array.

Rotate k elements

I know what you are thinking. We already know how to rotate an array by one element. All we need to do is run this function k times and we will get our answer. Although that is a viable solution, it would be quite a handful when the value of k is large. For example when k = 1000 we would end up calling the function 1000 times.

Let's step by step build a better solution. So to tackle the case when k is greater than n, we can simply use the modulus operator to bring it down to a number less than n.

[1, 2, 3, 4, 5]
// rotating the array n(5) times i.e. k = 5
[5, 1, 2, 3, 4]
[4, 5, 1, 2, 3]
[3, 4, 5, 1, 2]
[2, 3, 4, 5, 1]
[1, 2, 3, 4, 5] 
// As you can see we end up with the same array
// This means k = 5 will be same as k = 0,
// k = 6 will be same as k = 1,
// => f(k) = f(k % n)

Whenever we come across a k > n, we can simply take the modulo of the value and get it to k < n. So we solved the issue with k being a large value but what about k being a negative number?

[1, 2, 3, 4, 5]
// rotating the array -n(-5) times i.e. k = -5
[2, 3, 4, 5, 1] // same as k = 4
[3, 4, 5, 1, 2] // same as k = 3
[4, 5, 1, 2, 3] // same as k = 2
[5, 1, 2, 3, 4] // same as k = 1
[1, 2, 3, 4, 5] // same as k = 0
// => when 0 < k < n, 
// f(-k) = f(n-k) 
// and for k > n
// f(-k) = f(n-(-k % n))

You can check this relation with different values of k. Here is a simple implementation of this approach:

function k_cyc_rotate(arr, k) {
  let n = arr.length;
  let k_new;
  if (k < 0) {
    k_new = n - (-k % n);
  } else {
    k_new = k % n;
  }

  while (k_new--) {
    arr = cyc_rotate(arr);
  }

  return arr;
}

console.log(k_cyc_rotate([1, 2, 3, 4, 5], -3003))
-> [ 4, 5, 1, 2, 3 ]

This brings us to the end of this article. I hope you had as much fun as I had writing it. See you in the next article where we find out the maximum sum of contiguous subarray.

Cyclic Rotation of Array Elements

Table of contents

Rotate One Element

Rotate k elements