An array A is given, the task is to "right" rotate A by k places.
Example 1: Right rotate by 3 : {1, 2, 3, 4, 5, 6, 7}
Input: {1, 2, 3, 4, 5, 6, 7}
Output: {5, 6, 7, 1, 2, 3, 4}
Example 2: Right rotate by 2 : {10, 20, 43, 12, 7, 123}
Input: {10, 20, 43, 12, 7, 123}
Output: {7, 123, 10, 20, 43, 12}
Solutions
Method 1: Using extra space
We can solve this problem in O(n) time, using O(k) extra space.
Create an auxiliary array 'aux' of size k and copy A[n-k to n-1] elements to 'Aux'. Now traverse array A from n-k to 0; and right shift every element by (i+k).
0,0,0,0,1,1,1,2,2 0,0,1
Complexity
If k < n, the time complexity of this solution is (k + (n-k)+ k) or (n+k) or O(n); we have also used an auxiliary array 'aux' of size 'k', so space complexity is O(k).
Method 2: Reversal Algorithm
We can solve this problem in O(n) time and O(1) space, with the help of reversal algorithm.
In reversal algorithm - we first reverse A[0 to n-k-1] and A[n-k to n-1] and than reverse the whole array A[0 to n-1].
5,6,7,1,2,3,4 7,123,10,20,43,12
Complexity
The time complexity of this solution is O(n) and space complexity is O(1).
Method 3: In Place (No auxiliary array)
We can solve this problem in-place, without using any auxiliary array.
In this approach we need to right rotate the array by 1, k times; if value of k is n - we will be traversing it n times, so time complexity is O(n^2).
5,6,7,1,2,3,4 7,123,10,20,43,12
Complexity
Here the array is rotated by 1, k times; if value of k is n - it will be traversed n times, so time complexity is O(n^2).
Here no auxiliary array is used, yet the space complexity is O(k) only, because for every rotation a 'tmp' variable is used to store last element.