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.