## Problem:

Given an integer array and a number k , rotate the array by k positions to the right.

For example,

If the given array is

[1,2,3,4,5,6,7,8]

and k = 4

Then the output is

[5,6,7,8,1,2,3,4]

Pushing an element out of the array makes it land in the beginning of the array.

Try out the solution here:

https://leetcode.com/problems/rotate-array/

## Solution:

**Approach 1 – Use additional memory**

The solution is fairly straightforward using additional memory.

Create an array of the same size as the input.

Copy the last k elements in the first k positions in the result array.

Then copy the first n – k elements (n is the size of the array) into the remaining positions.

Once the result array is ready copy back the elements to the original array.

Here is the code:

```
class Solution {
public void rotate(int[] nums, int k) {
if(k > nums.length) k = k % nums.length ;
int[] result = new int[nums.length];
int index=0;
int start = nums.length - k;
for(int i=start;i<nums.length;i++){
result[index++] = nums[i];
}
for(int i=0;i<start;i++){
result[index++] = nums[i];
}
for(int i=0;i<result.length;i++){
nums[i] = result[i];
}
}
}
```

Notice that rotating an array of size n , n times places the elements in the same position as before.

So if k is greater than n , then we should find the modulus of k % n and perform that many number of rotations.

The time complexity in this approach is O(n) .

And space complexity is also O(n).

**Approach 2 – Using k additional memory**

Instead of using O(n) space complexity we can use constant space O(1).

In this approach we create an additional array of size k.

We will copy all the last k elements of the input array to this array.

Then we will move the remaining elements of the array to the end , making space for the k elements.

After this we copy the elements from the k array to the first k positions.

By doing this our space complexity is reduced.

Time complexity remains the same.

here is the code:

```
class Solution {
public void rotate(int[] nums, int k) {
if(k > nums.length ) k = k % nums.length;
int[] karray = new int[k];
int index = 0;
for(int i= nums.length - k ;i<nums.length;i++){
karray[index++] = nums[i];
}
int last = nums.length - k - 1;
int end = nums.length - 1;
while(last >=0){
nums[end] = nums[last];
end--;
last--;
}
for(int i=0;i<k;i++){
nums[i] = karray[i];
}
}
}
```

**Approach 3 – In place rotation**

In this approach , we are going to get rid of the k array as well.

There is no additional memory required.

Below is the algorithm:

- Reverse the entire array
- Reverse the first k elements of the reversed array
- Reverse the last n – k elements of the reversed array.

That gives us the required output.

Here is the code:

```
class Solution {
int[] nums;
public void rotate(int[] nums, int k) {
this.nums = nums;
if(k > nums.length) k = k % nums.length ;
reverse(0,nums.length-1);
reverse(0,k-1);
reverse(k,nums.length-1);
}
public void reverse(int first,int last){
while(first < last){
int t = nums[first];
nums[first] = nums[last];
nums[last] = t;
first++;
last--;
}
}
}
```

Time complexity is O(n) and space complexity is O(1)

That’s it!