You are given an integer array nums
. Your task is to rotate the array to the right by k
steps, where k
is a non-negative integer. It is important to perform this rotation in-place, meaning you should modify the original array directly without using extra space proportional to the size of the array.
Example 1:
nums = [1,2,3,4,5,6,7], k = 3
[5,6,7,1,2,3,4]
Explanation: Rotating to the right by 3 steps means each element shifts 3 positions to the right. The elements that reach the end wrap around to the beginning.Example 2:
nums = [-1,-100,3,99], k = 2
[3,99,-1,-100]
Explanation: Similarly, each element shifts 2 positions to the right, with wrap-around.Constraints:
nums
is between 1 and 10^5 (inclusive).nums
is between -2^31 and 2^31 - 1 (inclusive).k
is between 0 and 10^5 (inclusive).Describe an algorithm to efficiently rotate the array in-place. Consider both the time and space complexity of your solution. Can you identify any edge cases?
The most straightforward approach is to rotate the array one step at a time, repeating this process k
times. For each rotation, we shift every element to the right, with the last element moving to the first position.
Algorithm:
k
iterations:Code (Python):
def rotate_brute_force(nums, k):
n = len(nums)
for _ in range(k):
temp = nums[n - 1]
for i in range(n - 1, 0, -1):
nums[i] = nums[i - 1]
nums[0] = temp
Time Complexity: O(n*k), where n is the length of the array and k is the number of rotations. Each rotation takes O(n) time, and we perform k rotations.
Space Complexity: O(1). We use only a constant amount of extra space for the temporary variable.
A more efficient approach involves reversing sub-arrays of the original array. This method achieves the rotation in O(n) time.
Algorithm:
k
to its effective rotation count by taking k % n
, where n
is the length of the array.k - 1
.k
to the end of the array.Explanation:
Reversing the entire array puts the elements in reverse order. Then, reversing the first k
elements and the remaining n-k
elements places the last k
elements at the beginning of the array while preserving their order, and places the first n-k
elements after the k
elements, also preserving their order.
Code (Python):
def rotate_optimal(nums, k):
n = len(nums)
k %= n # Effective rotation count
def reverse(nums, start, end):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
reverse(nums, 0, n - 1) # Reverse entire array
reverse(nums, 0, k - 1) # Reverse first k elements
reverse(nums, k, n - 1) # Reverse remaining elements
Time Complexity: O(n), where n is the length of the array. We perform three reversals, each taking O(n) time.
Space Complexity: O(1). The reversal is done in-place, requiring only constant extra space.
k
is 0, no rotation is needed.k
is equal to the length of the array, no rotation is effectively needed (the array returns to its original state).k %= n
) handles cases where k
is larger than the array length, ensuring that the rotation is within the bounds of the array.The optimal reversal algorithm provides an efficient in-place solution for rotating an array by k
steps. It achieves O(n) time complexity and O(1) space complexity, making it a preferred choice over the brute-force approach.