## 189. Rotate Array

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

[show hint]

Hint:
Could you do it in-place with O(1) extra space?

Related problem: Reverse Words in a String II

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

b'
\n\n

## Summary

\n

We have to rotate the elements of the given array k times to the right.

\n

## Solution

\n
\n

#### Approach #1 Brute Force [Time Limit Exceeded]

\n

The simplest approach is to rotate all the elements of the array in k steps\n by rotating the elements by 1 unit in each step.

\n

Java

\n
public class Solution {\n    public void rotate(int[] nums, int k) {\n        int temp, previous;\n        for (int i = 0; i < k; i++) {\n            previous = nums[nums.length - 1];\n            for (int j = 0; j < nums.length; j++) {\n                temp = nums[j];\n                nums[j] = previous;\n                previous = temp;\n            }\n        }\n    }\n}\n
\n

Complexity Analysis

\n
\n
• Time complexity : . All the numbers are shifted by one step()\n k times().
• \n
• Space complexity : . No extra space is used.
• \n
\n
\n

#### Approach #2 Using Extra Array [Accepted]

\n

Algorithm

\n

We use an extra array in which we place every element of the array at its correct\nposition i.e. the number at index in the original array is placed at the\nindex . Then, we copy the new array to the original one.

\n

Java

\n
public class Solution {\n    public void rotate(int[] nums, int k) {\n        int[] a = new int[nums.length];\n        for (int i = 0; i < nums.length; i++) {\n            a[(i + k) % nums.length] = nums[i];\n        }\n        for (int i = 0; i < nums.length; i++) {\n            nums[i] = a[i];\n        }\n    }\n}\n
\n

Complexity Analysis

\n
\n
• \n

Time complexity : . One pass is used to put the numbers in the new array.\n And another pass to copy the new array to the original one.

\n
• \n
• \n

Space complexity : . Another array of the same size is used.

\n
• \n
\n
\n

#### Approach #3 Using Cyclic Replacements [Accepted]

\n

Algorithm

\n

We can directly place every number of the array at its required correct position.\nBut if we do that, we will destroy the original element. Thus, we need to store\nthe number being replaced in a variable. Then, we can place the replaced\n number() at its correct position and so on, times, where is\n the length of array. We have chosen to be the number of replacements since we have \n to shift all the elements of the array(which is ). But, there could be a problem with this method, if \n where (since a value of larger than eventually leads to a equivalent to ). In this case, while picking up numbers to be placed at the\n correct position, we will eventually reach the number from which we originally started. Thus, in such a case, when\n we hit the original number\'s index again, we start the same process with the number following it.

\n

Now let\'s look at the proof of how the above method works. Suppose, we have as the number of elements in the array and\n is the number of shifts required. Further, assume . Now, when we start placing the elements at their correct position, in the first cycle all the numbers with their index satisfying get placed at their required position. This happens because when we jump k steps every time, we will only hit the numbers k steps apart. We start with index , having . Thus, we hit all the numbers satisfying the above condition in the first cycle. When we reach back the original index, we have placed elements at their correct position, since we hit only that many elements in the first cycle. Now, we increment the index for replacing the numbers. This time, we place other elements at their correct position, different from the ones placed correctly in the first cycle, because this time we hit all the numbers satisfy the condition . When we hit the starting number again, we increment the index and repeat the same process from for all the indices satisfying . This happens till we reach the number with the index again, which occurs for . We will reach such a number after a total of k cycles. Now, the total count of numbers exclusive numbers placed at their correct position will be . Thus, all the numbers will be placed at their correct position.

\n

Look at the following example to clarify the process:\n nums: [1, 2, 3, 4, 5, 6]\nk: 2

\n

\n

java

\n
public class Solution {\n    public void rotate(int[] nums, int k) {\n        k = k % nums.length;\n        int count = 0;\n        for (int start = 0; count < nums.length; start++) {\n            int current = start;\n            int prev = nums[start];\n            do {\n                int next = (current + k) % nums.length;\n                int temp = nums[next];\n                nums[next] = prev;\n                prev = temp;\n                current = next;\n                count++;\n            } while (start != current);\n        }\n    }\n}\n
\n

Complexity Analysis

\n
\n
• \n

Time complexity : . Only one pass is used.

\n
• \n
• \n

Space complexity : . Constant extra space is used.

\n
• \n
\n
\n

#### Approach #4 Using Reverse [Accepted]

\n

Algorithm

\n

This approach is based on the fact that when we rotate the array k times, elements from the back end of the array come to the front and the rest of the elements from the front shift backwards.

\n

In this approach, we firstly reverse all the elements of the array. Then, reversing the first k elements followed by reversing the rest elements gives us the required result.

\n

Let and .

\n
Original List                   : 1 2 3 4 5 6 7\nAfter reversing all numbers     : 7 6 5 4 3 2 1\nAfter reversing first k numbers : 5 6 7 4 3 2 1\nAfter revering last n-k numbers : 5 6 7 1 2 3 4 --> Result\n
\n

java

\n
public class Solution {\n    public void rotate(int[] nums, int k) {\n        k %= nums.length;\n        reverse(nums, 0, nums.length - 1);\n        reverse(nums, 0, k - 1);\n        reverse(nums, k, nums.length - 1);\n    }\n    public void reverse(int[] nums, int start, int end) {\n        while (start < end) {\n            int temp = nums[start];\n            nums[start] = nums[end];\n            nums[end] = temp;\n            start++;\n            end--;\n        }\n    }\n}\n
\n

Complexity Analysis

\n
\n
• \n

Time complexity : . elements are reversed a total of three times.

\n
• \n
• \n

Space complexity : . No extra space is used.

\n
• \n
\n

Analysis written by: @vinod23

\n
'