Problem

Problem_Link

Solutions (time, space)

O(n), O(n)

class Solution {
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        int[] rtnNums = new int[len];

        // Rotate elements
        for (int i = 0; i < len; i++) {
            // Shift element by k positions
            rtnNums[(i + k) % len] = nums[i];
        }

        // Copy result array to original array
        System.arraycopy(rtnNums, 0, nums, 0, len);
    }
}

Explanation

what we want is [1,2,3,4]->[3,4,1,2] with k = 2

Thus, separate by [index 0 to k elements][index k to end elements] and put into a new array.

[1,2,3,4]->[1,2][3,4]->[3,4][1,2]->[3,4,1,2]

The elements of the array are rotated by iterating through the array and shifting each element by k positions. This is done by assigning the element at index i of the original array to the element at index (i + k) % len of the rtnNums array.

First Code

If improve this code, it will be above code.

class Solution {
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        int[] rtnNums = new int[len];

        //if k == nums.length, this is same as original nums.
        //if len=10 and k=14, this is same as len=10 and k=4
        if (k >= len) k = k % len;

        // copy rotating part to rtnNums
        if (k >= 0) System.arraycopy(nums, len - k, rtnNums, 0, k);
//        above code is same as blow
//        for (int i = 0; i < k; i++) {
//            rtnNums[i] = nums[len - k + i];
//        }


        // copy not rotating part to rtnNums
        if (len - k >= 0) System.arraycopy(nums, 0, rtnNums, k, len - k);
//        above code is same as blow
//        for (int i = 0; i < len - k; i++) {
//            rtnNums[i + k] = nums[i];
//        }

        //put back to original array
        System.arraycopy(rtnNums, 0, nums, 0, len);
//        above code is same as blow
//        for (int i = 0; i < len; i++) {
//            nums[i] = rtnNums[i];
//        }
    }
}

O(n), O(1)

class Solution {
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        // Normalize k because if k==len, is same as input array
        if (k >= len) k = k % len;

        // Reverse full array
        reverse(nums, 0, len - 1);
        // Reverse first k elements
        reverse(nums, 0, k - 1);
        // Reverse remaining elements
        reverse(nums, k, len - 1);
    }

    // Reverse array elements between start and end indices
    public static void reverse(int[] array, int start, int end) {
        while (start < end) {
            int temp = array[start];
            array[start] = array[end];
            array[end] = temp;
            start++;
            end--;
        }
    }
}

Explanation

what we want is [1,2,3,4]->[3,4,1,2] with k = 2

If we reverse all elements one time and reverse partial elements, it will be what we wanted

[1,2,3,4]->[4,3,2,1]->[3,4,2,1,]->[3,4,1,2]

1. The length of the array is calculated and stored in the variable len.

2. If k is greater than or equal to len, k is reduced modulo len to ensure that it is within the bounds of the array.

3. The reverse method is called on the entire array to reverse the elements of the array. [1,2,3,4]->[4,3,2,1]

4. The reverse method is called on the first k elements of the array to reverse them again. [4,3,2,1]->[3,4,2,1]

5. The reverse method is called on the remaining elements of the array to reverse them again. [3,4,2,1,]->[3,4,1,2]

Rotated Array

The array has been rotated by k positions.

The reverse method is a utility method that takes in an array and the indices between which the elements should be reversed. It swaps the elements at the start and end indices, and then increments the start index and decrements the end index until the start index is greater than the end index. This results in the elements between the start and end indices being reversed. The space complexity is O(1).