0189. Rotate Array

https://leetcode.com/problems/rotate-array

Description

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

Example 1:

**Input:** nums = [1,2,3,4,5,6,7], k = 3
**Output:** [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:** nums = [-1,-100,3,99], k = 2
**Output:** [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]

Constraints:

• 1 <= nums.length <= 105

• -231 <= nums[i] <= 231 - 1

• 0 <= k <= 105

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?

ac1: extra space

class Solution {
    public void rotate(int[] nums, int k) {
        // edge cases
        if (nums == null || nums.length <= 1) return;

        // init
        int len = nums.length;
        k = (k + len) % len;
        int[] tmp = new int[k];  // tmp array store k element

        int i =  len - 1, j = tmp.length - 1;
        // copy last k element to k array
        for ( ; i >= len - k; i--, j--) {
            tmp[j] = nums[i];
        }
        // move the rest in nums to the right
        int i2 = len - 1;
        for ( ; i >= 0; i--, i2--) {
            nums[i2] = nums[i];
        }
        // copy tmp back;
        i = 0;
        for (int j2 = 0; j2 < tmp.length; j2++, i++) {
            nums[i] = tmp[j2];
        }
    }
}
/*
O(n) time, O((k + len) % len) space

*/

ac2: in-place

class Solution {
    public void rotate(int[] nums, int k) {
        // edge cases
        if (nums == null || nums.length <= 1) return;

        k = (k + nums.length) % nums.length;

        // reverse entire array
        reverse(nums, 0, nums.length - 1);
        // reverse first k element
        reverse(nums, 0, k-1);
        // reverse the rest
        reverse(nums, k, nums.length - 1);

    }
    private void reverse(int[] nums, int s, int e) {
        // boudary check
        if (s >= e) return;

        while (s < e) {
            int tmp = nums[s];
            nums[s] = nums[e];
            nums[e] = tmp;
            s++;
            e--;
        }
    }
}
/*
O(n) time, O(1) space
*/