Problem
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative. The rotation should be performed in-place without using another array.Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
nums = [1,2,3,4,5,6,7]
k = 3Output
[5,6,7,1,2,3,4]Example 2
Input
nums = [-1,-100,3,99]
k = 2Output
[3,99,-1,-100]Solution
This solution uses the Two Pointer pattern with the array reversal technique.First, we normalize
k using k % nums.length because rotating an array by its length produces the same array. Then we reverse the entire array, reverse the first k elements, and finally reverse the remaining elements.
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k = k % n;
// Reverse the entire array.
reverse(nums, 0, n - 1);
// Reverse the first k elements.
reverse(nums, 0, k - 1);
// Reverse the remaining elements.
reverse(nums, k, n - 1);
}
private void reverse(int[] nums, int left, int right) {
while (left < right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
}Complexity
Each element is involved in the reversal operations a constant number of times, so the time complexity isO(n), where n is the length of the array.
The array is modified in-place and only a few variables are used, so the extra space complexity is
O(1).
