Rotate an array to the right by a given number of steps

Recently, I encountered this coding exercise on codility and the idea is

A zero-indexed array A consisting of N integers is given. Rotation of the array means that each element is shifted right by one index, and the last element of the array is also moved to the first place.

For example, the rotation of array A = [3, 8, 9, 7, 6] is [6, 3, 8, 9, 7]. The goal is to rotate array A K times; that is, each element of A will be shifted to the right by K indexes.


Write a function:

class Solution { public int[] CyclicRotation(int[] A, int K); }

that, given a zero-indexed array A consisting of N integers and an integer K, returns the array A rotated K times.


For example, given array A = [3, 8, 9, 7, 6] and K = 3


the function should return [9, 7, 6, 3, 8].

Assume that:


N and K are integers within the range [0..100];
each element of array A is an integer within the range [−1,000..1,000].

My approach was if the array has zero or 1 element, the array given is returned else thne for loop is executed. I also added the new array to extract a subset of the array which was meant to be shifted and the first element of Array A is swapped with the last element. Finally, a new list is created with aim to achieve the insert the first element A[0] after being swapped.

public static int[] CyclicRotation(int[] A, int K)
    {
        //Rotate an array to the right by a given number of steps.
        // eg k= 1 A = [3, 8, 9, 7, 6] the result is [6, 3, 8, 9, 7]
        // eg k= 3 A = [3, 8, 9, 7, 6] the result is [9, 7, 6, 3, 8]

        if(A.Length== 0 || A.Length ==1)
        {
            return A;
        }
        int lastElement;
        int[] newArray = new int[A.Length];

        List listOfNumbers = new List();

        for (int i = 1; i ();
            listOfNumbers.Insert(0, lastElement);

            A = listOfNumbers.ToArray();
            newArray = A;

        }
        return newArray;
    }

I believe there is room for im

In place solution

Jon Bentley "Programming Pearls" (1986) has this task as one of problems.

The recommended solution, instead of either:

• doing K 1-element rotations, using 1 temporary variable, with O(K N) time, which is slow

• using K-element temporary array, with O(N) time, which is wasteful... but only if there is requirement of doing it in place (and not returning copy, i.e. new N-element array)

is the Aha! solution of using reversals, with the following pseudocode

reverse(A, 0, K-1);
reverse(A, K, A.length()-1);
reverse(A, 0, A.length()-1);

assuming that reverse(A, I, J) operation reverses elements of array A from I-th element to J-th element, inclusive, that is, if $$A=\{a_0,a_1,...,a_i,a_{i+1}...,a_j,a_{j+1}...,a_{N-1}\}$$ then $$\text{reverse}(A, i,j)=\{a_0,a_1,...,a_j,...,a_{i+1},a_i,a_{j+1},...,a_{N-1}\}$$


For example, given array A = [3, 8, 9, 7, 6] and K = 3,
the function should return [9, 7, 6, 3, 8].

Steps, corrected for the account of different meaning for K, namely whether it is number of elements to move from left to right ("Programming Pearls"), or from right to left (an example):

• [3, 8,| 9, 7, 6] - original array

• [8, 3,| 9, 7, 6] - reversed first part

• [8, 3,| 6, 7, 9] - also reversed second part

• [9, 7, 6,| 3, 8] - the solution

The idea by @forsvarir, namely:


You're currently rotating the array by 1 over and over again. Instead, think about where each element will end up at the end of N rotations. It's end position should be something like (startPos + numberOfRotations) modulus array size.

is another possible algorithm for an in-place rotation in "Programming Pearls". It can be written in an elegant way, but coming up with correct implementation is a bit more tricky. Though it does twice less operations than the reverse based one, each operation is more complex; also it doesn't play well when N is large enough that swap must be used (nowadays probably not a problem).

Return copy solution

If you are returning a copy, you don't need a temporary K-element array. The solution is to create a result by copying appropriate parts.

In pseudocode (and in programming languages where you can do whole (sub)array copy) it would look like this:

Anew = allocate(N)
Anew[0:K-1] = A[N-K-1:N-1]
Anew[K:N-1] = A[0:N-K-1]

Here I assume that K means number of elements from the end to move to beginning, and that A[0:K-1] means array slice (a(1:K) in Fortran).

Note: I have not checked this solution - beware off-by-one errors here.

StackExchange Code Review Q#128871, answer score: 14