189. Rotate Array.md

Solution1

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

note

• time O(n) space O(1)
• The idea is to reverse subarray [0, k - 1] and [k, end] and then reverse the whole array. Say, we have an array of size 7 with k = 3 as the following [n - 4, n - 3, n - 2, n - 1, n, n + 1, n + 2]. So after rotating, we will have the following sequence: [n, n + 1, n + 2, n - 4, n - 3, n - 2, n - 1]. From the final status of the array, we will want to attach 'n + 2' with 'n - 4'. Thus, looking at the final array, it would make sense to reverse both subarray and reverse the whole array to get what expected result. With this example, it helps me to understand but it is not proved mathematically here.
• At the beginning, mod k with size of the array.