189. Rotate Array

Solution 1: Insert operation of the array (TLE)

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        for stepCnt in range(k):
            # Backup & Insert tail to head 
            backupOrigHead = nums[0]
            nums[0] = nums[-1]
            
            # Move the rest of array
            for idx in range(1, len(nums)):
                backupMovedElmt = nums[idx]
                nums[idx] = backupOrigHead
                backupOrigHead = backupMovedElmt
        return nums

Time Complexity: O(N*K) // Move the rest elements in array is O(N), and we do it K times
Space Complexity: O(1)

Solution 2: Use auxiliary array

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        rotatedArray = n*[0]
        for idx in range(n):
            rotatedIdx = (idx + k) % n
            rotatedArray[rotatedIdx] = nums[idx]
        nums[:] = rotatedArray
        return nums

Time Complexity: O(N)
Space Complexity: O(N)

Solution 3: Reverse 3 times (In-place)

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        def reverseInPlace(nums, start, end):
            while start < end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1
            return
        
        n = len(nums)
        rotateLen = k % n
        reverseInPlace(nums, 0, n - 1)
        reverseInPlace(nums, 0, rotateLen - 1)
        reverseInPlace(nums, rotateLen, n - 1)
        return nums

Time Complexity: O(N)
Space Complexity: O(1)

Solution 4: Cyclic Replacements

Time Complexity: O(N)
Space Complexity: O(1)

Reference

https://leetcode.com/problems/rotate-array/discuss/269948/4-solutions-in-python-(From-easy-to-hard)
https://leetcode.com/problems/rotate-array/discuss/54277/Summary-of-C%2B%2B-solutions