189.Rotate_Array_(Medium).md

189. Rotate Array (Medium)

Date and Time: Jul 6, 2024, 11:44 (EST)

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

Question:

Given an integer array nums, 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]

Edge case:

Input: nums = [1, 2], k = 3

Output: [2, 1]

KeyPoints:

The trick is that if we reverse [1, 2, 3, 4, 5, 6, 7] first, we have [7, 6, 5, 4, 3, 2, 1], then we reverse the first half from [:k] and the last half [k:] again we can get the rotated array [5, 6, 7, 1, 2, 3, 4].

We also need to be careful about k, we have to first use k = k % len(nuns) to get the final k. Look at Edge case: nums = [1, 2], k = 3, we move nums three times is the same as we move it one time (3 % 2 = 1). Also, if the times we need to move it is same as the length of nums (k = 0), we don't need to move.

Note: we have to modify nums in-place, so we can't do nums = nums[::-1] to reverse it, we have to use while loop to reverse.

Naive Solution:

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # Start from backward, save 7 into a var, then move each index right by 1, finally the last element in backward can be replaced with 7.
        i = 0
        while i < k:
            tmp = nums[len(nums)-1]
            for j in range(len(nums)-2, -1, -1):
                nums[j+1] = nums[j]
            nums[0] = tmp
            i += 1

Time Complexity: $O(n^k)$
Space Complexity: $O(1)$

Optimized Solution:

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def reverse(l, r):
            while l < r:
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
                r -= 1
        k = k % len(nums)
        # If k = len(nums), we don't need to modify
        if k != 0:
            reverse(0, len(nums)-1)  # Reverse nums
            reverse(0, k-1)  # Reverse nums[:k]
            reverse(k, len(nums)-1)   # Reverse nums[k:]

Time Complexity: $O(n^2)$
Space Complexity: $O(1)$