Rotate an Array using Constant Space

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

How it Works?

  • We rotate the array by n-1 times (that is what reverse does)
  • Next, we adjust the array partitions up to k and remaining elements. The adjustment means we reverse the partitions to undo excess rotation of n-1 rotation.

Reference

Written with StackEdit.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: