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

Question

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<int> listOfNumbers = new List<int>();

        for (int i = 1; i < K+1; i++)
        {

            lastElement = A[A.Length - 1];
            newArray = A.Take(A.Length - 1).ToArray(); 
            listOfNumbers = newArray.ToList<int>();
            listOfNumbers.Insert(0, lastElement);

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

        }
        return newArray;
    }

I believe there is room for improvements. Any suggestions would be appreciated.

Answer 1

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):

1. [3, 8,| 9, 7, 6] - original array
2. [8, 3,| 9, 7, 6] - reversed first part
3. [8, 3,| 6, 7, 9] - also reversed second part
4. [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.

Answer 2

Naming

Think about your variable naming. You've used listOfNumbers for your local variable, however your parameter names are A and K. Do they mean anything without looking at the rest of the code?

Break down the problem into methods

The code below looks like it represents rotating the array by 1 place. If so, put it in a method with an appropriate name, then call it. It will make the problem breakdown easier to follow.

lastElement = A[A.Length - 1];
newArray = A.Take(A.Length - 1).ToArray(); 
listOfNumbers = newArray.ToList<int>();
listOfNumbers.Insert(0, lastElement);

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

Think about the algorithm

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.

Answer 3

I think there is easier solution without creating additional arrays which only add overhead. All you want to do can be done using your original array and a few int variables. For example:

int len = A.Length; //self explanatory 
int tmp = A[len - 1]; //save last element value
for(int i = len-1;i > 0; i--) //starting from the end to begining
{
   A[i] = A[i - 1]; //assign value of the previous element
}
A[0] = tmp; //now "rotate" last to first.

This is just a fragment of code and further improvements are still possible. For example, you can rotate K times recursively.

Answer 4

My suggestion is to use the built-in Array.Copy static method to minimize allocation of additional memory:

private static void RotateArrayRight<T>(T[] array, int count)
{
    if (count < 0)
        throw new ArgumentOutOfRangeException("count");
    if (count == 0)
        return;

    // If (count == array.Length) there is nothing to do.
    // So we need the remainder (count % array.Length):
    count %= array.Length;

    // Create a temp array to store the tail of the source array
    T[] tmp = new T[count];

    // Copy tail of the source array to the temp array
    Array.Copy(array, array.Length - count, tmp, 0, count);

    // Shift elements right in the source array
    Array.Copy(array, 0, array, count, array.Length - count);

    // Copy saved tail to the head of the source array
    Array.Copy(tmp, array, count);
}

Usage:

int[] a = { 1, 2, 3, 4, 5, 6, 7 };
RotateArrayRight(a, 2);
// Now: a = { 6, 7, 1, 2, 3, 4, 5 }

---

The same approach with immutable source array:

private static T[] RotateArrayRight<T>(T[] array, int count)
{
    if (count < 0)
        throw new ArgumentOutOfRangeException("count");

    // If (count == array.Length) there is nothing to do.
    // So we need the remainder (count % array.Length):
    count %= array.Length;

    // Create a temp array to store the result
    T[] tmp = new T[array.Length];

    // Copy the last {count} elements of the source array to the head of the temp array
    Array.Copy(array, array.Length - count, tmp, 0, count);
    // Copy the rest elements
    Array.Copy(array, 0, tmp, count, array.Length - count);

    return tmp;
}

Usage:

int[] a = { 1, 2, 3, 4, 5, 6, 7 };
a = RotateArrayRight(a, 2);
// Now: a = { 6, 7, 1, 2, 3, 4, 5 }

Answer 5

You have an interface problem... caller passes an array and receives an array as return value. Is the return value meant to be a handle to the same array or a copy? Right now the behavior is inconsistent and depends on the size of the array argument.

    static void DumpArray(int[] array)
    {
        foreach (var element in array)
        {
            Console.Write(element);
            Console.Write(" ");
        }
        Console.WriteLine();
    }

    static void Main(string[] args)
    {
        {
            int[] untouchable = { 1, 2, 3 };
            DumpArray(untouchable);
            var rotated = CyclicRotation(untouchable, 2); // won't change "untouchable"
            rotated[0] = 9;
            DumpArray(untouchable); // good, still untouched
            DumpArray(rotated);
        }
        {
            int[] untouchable = { 1 };
            DumpArray(untouchable);
            var rotated = CyclicRotation(untouchable, 2); // won't change "untouchable"?
            rotated[0] = 9;
            DumpArray(untouchable);  // oh no! mutated!
            DumpArray(rotated);
        }
    }

    public static int[] CyclicRotation(int[] A, int K)
    {
        ...
    }

To make it consistent (and I think more intuitive), you can change the guard condition to if (A.Length == 0 || A.Length == 1) return (int[])A.Clone();. Better yet, rework your algorithm a bit and you won't need a special case.

Regardless, you should document the expected behavior and make sure your implementation actually follows through.

Answer 6

You could do the following:

var sample = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
var rotatedSample = Rotate(sample, 3);

protected static IEnumerable<int> Rotate(int[] source, int rotation)
{
     var temporary = source.Take(rotation);
     return source.SkipWhile(index => index <= rotation).Concat(temporary);
}

The benefit of this approach is simplicity. It will take based on the rotation, causing you to hold the original position's of your contents, but it will also shift the entire contents accordingly. Then you simply append the temporary to the end of the source, causing you to shift the entire array.

The performance may not be quite as quick as some other approaches, but the simplicity of syntax I feel is a valid trade off.

Answer 7

As others have mentioned, your solution is more involved (and slower) than necessary.

I would do this using an Int pointer that is an offset (mod "ArraySize") into the array, rather than actually moving elements within an array.

When you want to rotate the array, k steps to the right, then simply use k mod ArraySize.

When you need to access element N (0 for example) of array A, you read A[(0 + Offset) mod ArraySize].

The code below assumes that like the example in the original post, the "exercise" requires that the function has to return the original array (A), rotated, as a "new Array". If this is not really necessary, then the code below can be simplified even further.

I have also kept the same variable names you used in you example (A, k), because I assume those are the variable names given to you in the "exercise". Otherwise, consider making these names more descriptive.

Lastly, in your code, you have made a special case for when the size of the array (A) is "0 or 1". In the code below, these are handled naturally by the code and no special case treatment is necessary.

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

    //  int iOffset;
        int iArraySize=A.Length;
        int[] newArray = new int[iArraySize];

        for (int i = 0; i < iArraySize; i++)
        {
    //      iOffset=(k+i) % iArraySize;
    //      newArray[i] = A[iOffset];
            newArray[i] = A[(k+i) % iArraySize];
        }
        return newArray;
    }

Answer 8

Inefficient
In a loop you create 2 array, 1 list, and 1 insert at 0.
All of those are O(n) operations
You should not have any O(n) operations in the loop

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(K > arr.Lengh || k < 0) throw new Excetion();

    if(A.Length <=1 || K == 0)
    {
        return A.Clone();
    }

    // get a copy of the last k
    int[] last = new int[K];
    for (int i = 0; i < k; i++)
    {
        last[i] = A[a.A.Length - k + i];
    }

    // shift k 
    int[] newArray = new int[A.Length];
    for (int i = A.Length - 1; i >= k; i--)
    {
        newArray[i] = A[i - k];
    }

    // copy the last 3 back
    for (int i = 0; i < k; i++)
    {
        newArray[i] = last[i];
    }

    return newArray;
}

Answer 9

This is an excellent opportunity to use a LinkedList<int>.

To generalize the solution a bit, we can pass a boolean to a Rotate() method that determines the direction to rotate.

using System.Collections.Generic;
using System.Linq;

public class NumberArrayRotater
{
    public int[] Rotate(int[] numbers, int cycles, bool goRight)
    {
        var linkedList = new LinkedList<int>(numbers);
        if (goRight)
        {
            for (var i = 0; i < cycles; ++i)
            {
                var node = linkedList.Last;
                linkedList.RemoveLast();
                linkedList.AddFirst(node);
            }

            return linkedList.ToArray();
        }

        for (var i = 0; i < cycles; ++i)
        {
            var node = linkedList.First;
            linkedList.RemoveFirst();
            linkedList.AddLast(node);
        }

        return linkedList.ToArray();
    }
}

Also note that we could easily accept an IEnumerable<int> instead of an array.

Answer 10

There are two ways to do this - by the Programming Pearls swap trick, and by recursive rotation. The swap code is simpler to write and easier to prove, but the rotation code can be faster. Here's a worked example of each algorithm.

#include <stdio.h> 
#include <stdlib.h> 

// Rotate a subset of a array 

//           0 1 2 3 4 5 6 7 8 9 
// eg rotate A B C D E F G H I J, 2, 3, 8 
//               \_/ \_______/ 

// =>        A B E F G H I C D J 
//               \_______/ \_/ 


void reverse(int *A, int low, int high) 
{ 
  while (low < high) { 
    register int temp = A[low]; 
    A[low++] = A[high]; 
    A[high--] = temp; 
  } 
} 

void rotate_by_reversals(int *A, int first_index, int rot_index, int last_index) 
{ 
  //               f r         l 
  //           0 1 2 3 4 5 6 7 8 9 
  // eg rotate A B C D E F G H I J, 2, 3, 8 
  //               \_/ \_______/ 
  // =>        A B E F G H I C D J, 2, 3, 8 
  //               \_______/ \_/ 



  if (first_index == rot_index || rot_index+1 == last_index) return; 
  reverse(A, first_index, rot_index); 
  //               f r         l 
  //           A B C D E F G H I J 
  //               \_/ 
  // =>        A B D C E F G H I J 

  reverse(A, rot_index+1, last_index); 
  //               f r         l 
  //           A B D C E F G H I J 
  //                   \_______/ 
  // =>        A B D C I H G F E J 

  reverse(A, first_index, last_index); 
  //               f r         l 
  //           0 1 2 3 4 5 6 7 8 9 
  //           A B D C I H G F E J 
  //               \___________/ 

  // =>        A B E F G H I C D J 
  //               \___________/ 

} 

void swap_blocks(int *A, int left, int right, int len) 
{ 
  // preserve order 
  while (len-- > 0) { 
    register int temp = A[left]; 
    A[left++] = A[right]; 
    A[right++] = temp; 
  } 
} 

void rotate_by_blocks(int *A, int first_index, int rot_index, int last_index) 
{ 
  int len; 
  while (first_index != last_index) { // while loop replaces recursion
  if (rot_index-first_index+1 < last_index-rot_index) { 

    len = rot_index-first_index+1; 

    //               f r         l 
    //           0 1 2 3 4 5 6 7 8 9 
    // eg rotate A B C D E F G H I J, 2, 3, 8 
    //               \_/ \_______/ 

    // =>        A B E F G H I C D J 
    //               \_______/ \_/ 


    swap_blocks(A, first_index, rot_index+1, len); 
    //               f r         l 
    //           0 1 2 3 4 5 6 7 8 9 
    //           A B C D E F G H I J 
    //               \_/ \_/ 
    // =>        A B E F C D G H I J 
    //               \_/ \_/ 

    // rotate_by_blocks(A, rot_index+1, rot_index+len, last_index); 
                           first_index = rot_index+1; 
                                        rot_index += len; 
    //               f r         l 
    //           A B E F C D G H I J 
    //                   \_/ \___/ 
    // =>        A B E F G H I C D J 
    //                   \___/ \_/ 

  } else { 
    len = last_index-rot_index; 
    //               f       r   l 
    //           0 1 2 3 4 5 6 7 8 9 
    // eg rotate A B C D E F G H I J, 2, 6, 8 
    //               \_______/ \_/ 
    // =>        A B H I C D E F G J 
    //               \_/ \_______/ 


    swap_blocks(A, rot_index-len+1, last_index-len+1, len); // or rot_index, last_index, -len ??? 
    //               f       r   l 
    //           0 1 2 3 4 5 6 7 8 9 
    //           A B C D E F G H I J 
    //                     \_/ \_/ 
    // =>        A B C D E H I F G J 

    // rotate_by_blocks(A, first_index, rot_index-len, rot_index); 
                                                       last_index = rot_index; 
                                        rot_index -= len; 
    //               f       r   l 
    //           A B C D E H I F G J 
    //               \___/ \_/ 
    // =>        A B H I C D E F G J 
    //               \_/ \___/ 
  } 
  } 
} 

int main(int argc, char **argv) { 
  int fred[10], i; 

  for (i = 0; i < 10; i++) fred[i] = i+'A'; 
  fprintf(stdout, "rotate_by_reversals(ABCDEFGHIJ, 2, 3, 8) => "); 
  rotate_by_reversals(fred, 2, 3, 8); 
  for (i = 0; i < 10; i++) putchar(fred[i]); putchar('\n'); 

  for (i = 0; i < 10; i++) fred[i] = i+'A'; 
  fprintf(stdout, "rotate_by_blocks(ABCDEFGHIJ, 2, 3, 8) => "); 
  rotate_by_blocks(fred, 2, 3, 8); 
  for (i = 0; i < 10; i++) putchar(fred[i]); putchar('\n'); 

  exit(0); 
  return(1); 
}