Leetcode 189: Rotate Array to the Right by K Times

$\mathtt{REFERENCE}$ @ LeetCode

Problem Definition

You are given an array and integer $k$ (>= 0). The problem is to rotate the input array to the right by $k$ times. Details can be found at LeetCode.

Example

Input: [1,2,3,4,5,6,7] and k = 3

Output: [5,6,7,1,2,3,4]

Solution 1 : Using Auxiliary Array of Size Same as Input Array.

In this method we go on saving the elements to the new rotated location in the auxiliary array. Finally when all elements are rotated to their proper indices, all elements are copied back to the original array in the same order as they appear after rotation.

Complexity

This method takes $\cal{O(n)}$ Time and $\cal{O(n)}$ Space.

Implementation

Solution 2 : Using Auxiliary array of size k

In the first solution we have used auxiliary array of size same as input to store rotated elements. If we look carefully, we can move in place those elements which can be pushed to right from left. Only those rightmost $k$ elements which can not be moved right cannot be moved in place because they have potential to replace the elements which have not been moved.

So it is sufficient to save only the right most $k$ elements in the auxiliary space. This will reduce the space requirement from ${O(n)}$ to ${O(k)}$.

In this method we use auxiliary array of size $k$ only. Rotation of the first $(N - k)$ elements will be done in place. Rotation of the last $k$ elements is stored in the auxiliary array. Once all elements are done, elements from the auxiliary array are copied in the front of input array.

Complexity

This method takes $\cal{O(n)}$ Time and $\cal{O(k)}$ Space.

Implementation

Solution 3 : Using Reversal Algorithm

The solutions we discussed above uses auxiliary array of some size to solve the problem. Hence they have certain extra space requirement.

Here we are going to discuss a solution that does not use any extra space. So this is a constant space solution.

Here we divide the input array into two parts

1. First $(N - k)$ elements
2. and Last $k$ elements

Now,

1. Reverse the first part of the array.
2. Reverse the second part.
3. Reverse the whole array. Result will the required rotation of the array by $k$ times to the right.

Complexity

In this method we have managed to reduce the space complexity from O(n) to a constant space. This method still takes $\cal{O(n)}$ Time but $\cal{O(1)}$ Space.

Implementation

---

---

---