Rotate an Array

Given an array of integers. Rotate the array by k position to right (or left).

For example, given array A=[1,2,3,4,5,6] then rotateRight(A, 2) will return [5, 6, 1, 2, 3, 4] and rotateLeft(A,2) will return [3, 4, 5, 6, 1, 2]. Also, otateRight(A, 8) will return [5, 6, 1, 2, 3, 4] because after k=length of array(=6) the rotated array will be same as original array.

Trivial Solution
We can see that in order to rotate right by k we need to shift the array right by k%n to make k%n space on the left so that the last k%n elements of the original array can be placed there. So, trivial solution will be to use a temp array of size k%n to save the rightmost k%n elements and then shift the array to right by k%n position. Then copy back the saved element from temp array to the left of the the original array. Overall procedure will take O(n) time and O(n) space due to the use of temp array. Similarly we can do left rotation.

Can we do better in O(1) space
Note that we can do in place swapping of element of rotated part with the positions it have to go after rotation. It will however displace the elements that have been swapped from left to right to make space for rotated element. We need to do some more swap to go back to original order. Following is the whole procedure –

Let, n = length of array and d = number of rotations
so, we need to rotate right A by d%n.

So, position of the start of rotation k = n-(d%n)
initially i = 0, j = k, and we traverse left to right as follows - 

1, 2, 3, 4, 5, 6
^           ^
i           j,k       --> swap(i, j), increment i, j

5, 2, 3, 4, 1, 6      
   ^        ^  ^
   i        k  j      --> swap(i, j), increment i, j (j will be wrapped around k)

5, 6, 3, 4, 1, 2      
      ^     ^
      i     j,k       --> swap(i, j), increment i, j

5, 6, 1, 4, 3, 2      
         ^  ^  ^
         i  k  j      --> swap(i, j), increment i, j (j will be wrapped around k)

5, 6, 1, 2, 3, 4      
            ^
            i,j,k     --> we stop when i and j meet

Similarly for left rotation we can do as follows –

Let, n = length of array and d = number of rotations
so, we need to rotate left A by d%n.

So, position of the start of rotation k = (d%n)-1
initially i = n-1, j = k and we traverse right to left as follows - 

1, 2, 3, 4, 5, 6
   ^           ^
   j,k         i     --> swap(i, j), decrement i, j

1, 6, 3, 4, 5, 2
^  ^        ^
j  k        i        --> swap(i, j), decrement i, j (j will be wrapped around k)

5, 6, 3, 4, 1, 2
   ^     ^
   j,k   i           --> swap(i, j), decrement i, j 

5, 4, 3, 6, 1, 2
^  ^  ^
j  k  i              --> swap(i, j), decrement i, j (j will be wrapped around k)

3, 4, 5, 6, 1, 2
   ^
   i,j,k            --> we stop when i and j meet

Now, does the above technique works in all cases? What about right rotation A=[1,2,3,4,5,6,7,8,9,10] by d=7. What will happen? We will see that the above technique works if and only if when start position of a rotation, k falls in of right half of the array for right rotation. This is due to the fact that rotation right by more that n/2 positions yields a left rotation by less that n/2 position. This property is symmetric. So, we during right rotation we can check if we can do less swap by doing a left rotation of less number of rotations and hence swap.

Below is the implementation of the above idea which runs in O(n) time and O(1) space.

public static void rotateRight(int[] A, int d){
	int n = A.length;
	
	int i = 0;
	int k = n - (d%n);
	int j = k;
	
	if(k < n/2){
		rotateLeft(A, n-d);
		return;
	}
	
	while(i < j){
		swap(A, i, j);
		i++;
		j = (j == n-1) ? k : j+1;
	}
}

public static void rotateLeft(int[] A, int d){
	int n = A.length;
	
	int i = n-1;
	int k = d%n-1;
	int j = k;
	
	if(k > n/2){
		rotateRight(A, n-d);
		return;
	}
	
	while(j < i){
		swap(A, i, j);
		i--;
		j = (j == 0) ? k : j-1;
	}
}

Can we minimize number of swaps with along with O(1) space

Note that we can do rotate by some simple in-place reverse using swaps only as follows –

A=[1, 2, 3, 4, 5, 6]  and k=2 
               ^
               rotation point

1. Reverse unrotated part A[..n-k-1]
A=[4, 3, 2, 1, 5, 6]
               ^

2. Reverse rotated part A[n-k..]
A=[4, 3, 2, 1, 6, 5]
               ^

3. Reverse the whole array 
A=[5, 6, 1, 2, 3, 4]

So, we can rotate an array using 3 simple O(n) reverse using only in-place swaps. Below is the O(n) time and O(1) space implementation of this idea.

public static void rotateRight(int[] A, int k){
	int n = A.length;
	if(n <= 1){
		return;
	}
	
	k = k%n;
	
	if(k == 0){
		return;
	}
	
	//reverse non rotated part
	reverse(A, 0, n-k-1);
	//reverse rotated part
	reverse(A, n-k, n-1);
	//reverse the whole array
	reverse(A, 0, n-1);
}

public static void rotateLeft(int[] A, int k){
	int n = A.length;
	if(n <= 1){
		return;
	}
	
	k = k%n;
	
	if(k == 0){
		return;
	}
	
	//reverse the whole array
	reverse(A, 0, n-1);
	//reverse rotated part
	reverse(A, n-k, n-1);
	//reverse non rotated part
	reverse(A, 0, n-k-1);
}

public static void reverse(int A[], int i, int j){
	while(i < j){
		swap(A, i, j);
		i++;
		j--;
	}
}