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]

Algorithm

If you draw a diagram like this and check for the change of indexes, it is fairly simple:

0 1 2 3 4 5 6   -> index                
1 2 3 4 5 6 7   -> Original ( n = 7 )
^^^^^^
5 6 7 1 2 3 4   -> rotate right by 3 (k = 3)
         ^^^^^^

This operation is equivalent to three operations
1. Create a destination array with the same length
1. Copy from position '0' of original to destination '3' of length '4' // 0 -> position k of length n-k
2. Copy from position '4' of original to destination '0' of length '3' // n-k -> position 0 of length k

Solution (Rotate right)

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution { public void rotate(int[] nums, int k) { if (k > nums.length) k = k % nums.length; int[] result = new int[nums.length]; System.arraycopy(nums, nums.length - k, result, 0, k); System.arraycopy(nums, 0, result, k, nums.length - k); System.arraycopy(result, 0, nums, 0, nums.length); } }

Performance

Same algorithm apply to rotation left
0 1 2 3 4 5 6   -> index
1 2 3 4 5 6 7   -> Original
^^^^
4 5 6 7 1 2 3   -> rotate left by 3
            ^^^^

Solution (Rotate left)

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution { public void rotate(int[] nums, int k) { if (k > nums.length) k = k % nums.length; int[] result = new int[nums.length]; System.arraycopy(nums, k, result, 0, nums.length - k); System.arraycopy(nums, 0, result, nums.length - k, k); System.arraycopy(result, 0, nums, 0, nums.length); } }

Although this solution has space complexity O(n) because I make a copy of the original array.

Here's an solution of space O(1):

Algorithm:

We make use the following properties for rotation right

1 2 3 4 5 6 7
4 3 2 1 5 6 7      1. reverse the first n-k elements
4 3 2 1 7 6 5      2. reverse the last k elements
5 6 7 1 2 3 4      3. reverse the whole array

How about rotate left ?

1 2 3 4 5 6 7
3 2 1 4 5 6 7      1. reverse the first k elements
3 2 1 7 6 5 4      2. reverse the last n-k elements
4 5 6 7 1 2 3      3. reverse the whole array

Solution for rotate right:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

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

The shortcoming is that this algorithm runs quite slow in Java