Rotate Array to the Right [Solution]
Below is the solution to the Rotate Array problem in Python, including comments and explanations.
from typing import List
def rotate_array(nums: List[int], k: int) -> None:
"""
Rotate the array to the right by k steps.
Parameters:
- nums: List of integers representing the array.
- k: Number of steps to rotate the array.
Returns:
- None: The function should modify the input list in-place.
"""
# Calculate the effective rotation steps by taking the remainder
# This is to handle cases where k is greater than the length of the array
k = k % len(nums)
# Reverse the entire array
reverse(nums, 0, len(nums) - 1)
# Reverse the first k elements
reverse(nums, 0, k - 1)
# Reverse the remaining elements
reverse(nums, k, len(nums) - 1)
def reverse(nums: List[int], start: int, end: int) -> None:
"""
Helper function to reverse a portion of the array in-place.
Parameters:
- nums: List of integers representing the array.
- start: Starting index of the portion to be reversed.
- end: Ending index of the portion to be reversed.
Returns:
- None: The function should modify the input list in-place.
"""
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
# Example usage:
nums = [1, 2, 3, 4, 5, 6, 7]
rotate_array(nums, 3)
print(nums)
assert nums == [5, 6, 7, 1, 2, 3, 4], "nums should be [5, 6, 7, 1, 2, 3, 4]"
nums = [-1, -100, 3, 99]
rotate_array(nums, 2)
print(nums)
assert nums == [3, 99, -1, -100], "nums should be [3, 99, -1, -100]"
Time Complexity:
The time complexity is O(n
), where n
is the length of the array.
The three reverse operations each take O(n/3
) time, which simplifies to
O(n
) in big-O notation.
Space Complexity:
The space complexity is O(1
) since the algorithm modifies the input array
in-place and does not use any additional data structures whose size depends on
the input.