[Leetcode] 189. Rotate Array

https://leetcode.com/problems/rotate-array/description/?envType=study-plan-v2&envId=top-interview-150

initial

I didnt know how so I looked at solution 2 days ago. We cant return anything along the solution and only can modify the given list so I did it like this where you reverse from 0 to kth index, from k+1 to end and from start to end. BUT there is a prob

        reverse(0, k)      # reverse(0, 2)
        reverse(k + 1, len(nums) - 1) # reverse(3, 3)
        reverse(0, len(nums) - 1) # reverse(0, 3)

lets look at this case

[-1,-100,3,99]

If I reverse via (0,k) it reverses the first 3 elements while the second reverse does practically nothing. But thats wrong logic as we want to reverse from (0,2) and (2,3). So the correct way is reverse up till n-k-1.

solution

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

complexity

time is 2*n cuz we reverse the list twice. space is o(1)