Description

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example 1:

1Input: nums = [1,2,3,4,5,6,7], k = 3
2Output: [5,6,7,1,2,3,4]
3Explanation:
4rotate 1 steps to the right: [7,1,2,3,4,5,6]
5rotate 2 steps to the right: [6,7,1,2,3,4,5]
6rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

1Input: nums = [-1,-100,3,99], k = 2
2Output: [3,99,-1,-100]
3Explanation: 
4rotate 1 steps to the right: [99,-1,-100,3]
5rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

  • 1 <= nums.length <= 10^5
  • -2^31 <= nums[i] <= 2^31 - 1
  • 0 <= k <= 10^5

Follow up:

Try to come up with as many solutions as you can. There are at least three different ways to solve this problem. Could you do it in-place with O(1) extra space?

Solution

Brute force approach

The brute force approach would be to rotate the array as many times as needed. One optimization is if the value of k is more than nums.length then we will be iterating over the array more than once. So, we can reduce that to required number of times because going over full array once will bring th array in the original state. So, we have to iterate only k % nums.length times.

 1class Solution {
 2    public void rotate(int[] nums, int k) {
 3        k = k % nums.length;
 4        int temp, prev;
 5        for (int i = 0; i < k; i++) {
 6            prev = nums[nums.length - 1];
 7            for (int j = 0; j < nums.length; j++) {
 8                temp = nums[j];
 9                nums[j] = prev;
10                prev = temp;
11            }
12        }
13    }
14}

Optimized solution

Another option is to rotate only required elements and come to required state. If we look at it carefully, we can come to required state by following below steps. Again, we should rotate only k % nums.length times only. Below is example walk through for nums = [1, 2, 3, 4, 5, 6, 7] and k = 3.

  1. Reverse first n - k elements first. This results into [4,3,2,1, 5,6,7]
  2. Reverse last k elements. This results into [4,3,2,1, 7,6,5]
  3. Now reverse the entire array. [5,6,7, 1,2,3,4]

The third step can be even performed first, followed by step 1 and 2. That will also result in the same output.

 1class Solution {
 2    public void rotate(int[] nums, int k) {
 3        // In this case, the rotation will not change array
 4        if(nums.length == 0 || (k % nums.length) == 0) {
 5            return;
 6        }
 7
 8        k = k % nums.length;
 9
10        int n = nums.length;
11
12        // Reverse entire array, O(n / 2)
13        reverse(nums, 0, n);
14
15        // Flip first k numbers
16        reverse(nums, 0, k);
17
18        // Reverse last n-k numbers
19        reverse(nums, k, n);
20    }
21
22    // use two pointers to reverse the array in O(n / 2) time.
23    private void reverse(int[] nums, int startIndex, int endIndex) {
24        for (int i = endIndex - 1, j = startIndex; i > j; i--, j++) {
25            int temp = nums[i];
26            nums[i] = nums[j];
27            nums[j] = temp;
28        }
29    }
30}