Rotating array

Problem

Write a function to rotate given array clock-wise. i.e. Rotate(int[] a, int k)

Approaches

1. One obvious approach is by using extra memory of 'k', and then rotating the array - it is O(N) and O(k) space.

 

2. Rotating array by '1' and repeating the task for 'k' number of times

 

Below is the approach of achieving the result in O(N) and O(1) space:

 

a. Firstly, reverse the array

b. And then reverse first 'k' elements and reverse remaining elements separately.

 

 

Code Snippet

14. void swap<T>(ref T x, ref T y)
15.         {
16.             T t = x;
17.             x = y;
18.             y = t;
19.         }
20.         void Reverse(int[] a, int start, int end)
21.         {
22.             int i = start, j = end;
23.             while (i < j)
24.             {
25.                 swap<int>(ref a[i], ref a[j]);
26.                 i++;
27.                 j--;
28.             }
29.         }
30.         void Rotate(int[] a, int k)
31.         {
32.             a.ThrowIfNull("array");
33.             k.Throw("k", e => e < 0);
34.             if (a.Length <= 1)
35.             {
36.                 return;
37.             }
38.             k = k % a.Length;
39.             this.Reverse(a, 0, a.Length - 1);
40.             this.Reverse(a, 0, k - 1);
41.             this.Reverse(a, k, a.Length - 1);
42.         }

Unit Tests

Code Snippet

44. [TestMethod]
45.         public void RotateTests()
46.         {
47.             int[] a = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
48.             for (int i = 1; i <= a.Length; i++)
49.             {
50.                 int k = a.Length - i + 1;
51.                 int[] b = new int[a.Length];
52.                 this.Rotate(a, i);
53.                 for(int j = 0;j<b.Length;j++)
54.                 {
55.                     if(k > a.Length)
56.                     {
57.                         k = (k % a.Length);
58.                     }
59.                     b[j] = k;
60.                     k++;
61.                 }
62.                 for (int j = 0; j < a.Length;j++ )
63.                 {
64.                     Assert.IsTrue(a[j] == b[j]);
65.                 }
66.                 this.Rotate(a, a.Length - i);
67.             }
68.         }

References

http://www.geeksforgeeks.org/program-for-array-rotation-continued-reversal-algorithm/