SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Intuition

To rotate an array to the right by k steps, each element of the array needs to be shifted to the right by k positions. This operation can be performed efficiently by reversing parts of the array. By reversing the entire array, and then reversing the two segments created by the split at position k, the array can be rotated in place without needing extra space.

Approach

1. Calculate k % n to handle cases where k is greater than the length of the array.
2. Reverse the entire array.
3. Reverse the first k elements.
4. Reverse the remaining n - k elements.

These steps ensure that the array is rotated to the right by k positions.

Complexity

Time Complexity

The time complexity is O(n), where n is the length of the array. This is because reversing the array or parts of it takes linear time.

Space Complexity

The space complexity is O(1) since we are modifying the array in place and not using any extra space that scales with the input size.

Code

C++

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n; // In case k is greater than the size of nums
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

Python

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        l = len(nums)
        dif = 0
        if k > l:
          k = k-l*(k//l)
        for i in range(l-k):
          nums.append(nums[i-dif])
          nums.pop(i-dif)
          dif += 1

Java

class Solution {
    public void rotate(int[] nums, int k) 
    {
        int n = nums.length;
        k = k % n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 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--;
        }
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    if(k > nums.length) {
        k = k%nums.length;
    }
    nums.unshift(...nums.splice(-1*k));
};