## Similar Problems

Similar Problems not available

# Rotate Array - Leetcode Solution

LeetCode: Rotate Array Leetcode Solution

Difficulty: Medium

Topics: math array two-pointers

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.

## Rotate Array Solution Code

`1`