Leetcode 189. Rotate Array

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Follow up:

• Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

First way is by doing slicing:

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

        if k <= 0:
            return

        k = k % len(nums)

        first_portion = nums[0:len(nums)-k]
        second_portion = nums[len(nums)-k:]

        nums[0:k] = second_portion
        nums[k:] = first_portion

Second way is reversing the array and reversing the first k elements again the reversing the rest

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

        if k <= 0:
            return

        k = k % len(nums)

        self.reverse(nums, 0, len(nums))
        self.reverse(nums, 0, k)
        self.reverse(nums, k, len(nums) - k)


    def reverse(self, nums: List[int], start: int, length: int) -> None:
        end = start + length - 1

        for i in range(start, start + int(length/2)):
            temp = nums[i]
            nums[i] = nums[end - i + start]
            nums[end-i+start] = temp

Better way to do reverse

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

        if k <= 0:
            return

        k = k % len(nums)
        l, r = 0, len(nums) - 1

        self.reverse(nums, l, r)
        self.reverse(nums, l, k - 1)
        self.reverse(nums, k, len(nums) - 1)

    def reverse(self, nums: List[int], l: int, r: int) -> None:
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l, r = l + 1, r - 1