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

Example 1:

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

Example 2:

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

Note:

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

 

 

 

Solution 1 - Intermediate Array

Space is O(n) and time is O(n). 

class Solution {    public void rotate(int[] nums, int k) {        if(nums == null){            return;        }        if(k >= nums.length){            k = k % nums.length;        }        int[] temp = new int[nums.length];        int count=0;        for(int i=nums.length-k; i

 

Solution 2 - Bubble Rotate

O(1) space,O(n*k) time

class Solution {    public void rotate(int[] nums, int k) {        if(nums == null){            return;        }        if(k >= nums.length){            k = k % nums.length;        }        for (int i=0; i
     
       0; j--){                int temp = nums[j-1];                nums[j-1] = nums[j];                nums[j] = temp;            }                    }                    }}
     

 

Solution 3 - Reversal

Can we do this in O(1) space and in O(n) time? The following solution does.

Assuming we are given {1,2,3,4,5,6} and order 2. The basic idea is:

1. Divide the array two parts: 1,2,3,4 and 5, 62. Reverse first part: 4,3,2,1,5,63. Reverse second part: 4,3,2,1,6,54. Reverse the whole array: 5,6,1,2,3,4

class Solution {    public void rotate(int[] nums, int k) {        if(nums == null){            return;        }        if(k >= nums.length){            k = k % nums.length;        }        reverse(nums, 0, nums.length-k-1);        reverse(nums, nums.length-k, nums.length-1);        reverse(nums, 0, nums.length-1);    }        public void reverse(int[] nums, int left, int right){        if(nums == null || nums.length == 1){            return;        }        while(left < right){            int temp = nums[left];            nums[left] = nums[right];            nums[right] = temp;            left++;            right--;        }    }}