[Leetcode] 189. Rotate Array

Medium level

 

Intuition:

 

It seems like a trivial question. I can just slice the array into two subarrays, and reference the input list to point to a combination of the two subarrays.

 

My solution:

 

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

 

Pretty self explanatory. The problem is that space complexity is O(n), because concatenating the two slices requires allocating memory for the new list of size n. Runtime is also O(n) since slice operations takes the size of the arrays.

 

Most Upvoted:

 

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

 

This has O(n) time complexity, and O(1) space complexity.

It's widly not intuitive at first, but basically, we divide the given array into 2 parts along where the k elements are supposed to be split into. So for Nums [1,2,3,4,5,7,8] and k =3, p1 would be the first 4 elements, and p2 would be the last 3. Then we reverse the p1, and then reverse p2, then finally reverse the entire array as a whole.

 

While it's easy retrospectively, this problem really doesn't fit into an existing algorithm and requires you to figure out the trick in place. It's super clever though.