Rotate Array - Leetcode Solution

Problem:

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

Example 1:

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]

Example 2:

Input: nums = [-1,-100,3,99], k = 2

Output: [3,99,-1,-100]

Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]

Solution:

The most straightforward way of rotating an array is to perform k rotations. In each rotation, we move the last element of the array to its beginning. We repeat this operation k times. However, this approach has a time complexity of O(k * n) and can time out for large k values.

The optimal way of performing array rotation is to use the reverse approach. First, we reverse the entire array. Then, we reverse the first k elements of the array and then the last n-k elements of the array. This approach has a time complexity of O(n) and does not time out even for large k values.

For example, let's say we have an array of 7 elements and k=3. After reversing the entire array, the array will be: [7, 6, 5, 4, 3, 2, 1]. We then reverse the first k elements of the array: [5, 6, 7, 4, 3, 2, 1]. Finally, we reverse the last n-k elements of the array: [5, 6, 7, 1, 2, 3, 4], which is the required output.

The code for the solution can be written as follows:

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

In this code, we first calculate the value of k modulo n to handle the cases where k is greater than n. We then call the reverse function three times. The first time, we reverse the entire array. The second time, we reverse the first k elements of the array, and the third time, we reverse the last n-k elements of the array.

1