[Coderust] Rotate Array

 

 

Problem

 

 

---

Reverse the whole array.

Divide the array by k index, and reverse the two subarrays.

 

ex) 

k=3

1 2 3 4 5 6 7

-> 7 6 5 4 3 2 1

-> 7 6 5 | 4 3 2 1

-> 5 6 7 | 1 2 3 4

 

Solution

 

 

Time Complexity

O(N)

 

 

Space Complexity

O(1)

 

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
       
        k %= len(nums)   
        nums = self.reverse(nums, 0, len(nums)-1)
        nums = self.reverse(nums, 0, k-1)
        nums = self.reverse(nums, k, len(nums)-1)
    
    
    def reverse(self, a: List[int], start: int, end: int) -> List[int]:
        while start<end:
            a[start], a[end] = a[end], a[start]
            start += 1
            end -= 1
            
        return a

 

 

 

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        l = len(nums)
        result = [0] * l
        for i in range(l):
            result[(i+k)%l] = nums[i]
            
        for i in range(l):
            nums[i] = result[i]

This is also a valid solution but has space complexity of O(N).