Description
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
Examples:
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 in Python
Python
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# Step 1: Handle the case where k is greater than the length of the array
# We use modulo operation because rotating by the length of the array brings the array back to its original state.
k = k % len(nums)
# Step 2: Reverse the entire array
self.reverse(nums, 0, len(nums) - 1)
# Step 3: Reverse the first k elements
self.reverse(nums, 0, k - 1)
# Step 4: Reverse the remaining elements
self.reverse(nums, k, len(nums) - 1)
def reverse(self, nums: List[int], start: int, end: int) -> None:
"""
Helper function to reverse elements in the array between start and end indices.
"""
while start < end:
# Swap the elements at start and end
nums[start], nums[end] = nums[end], nums[start]
# Move the pointers towards the center
start += 1
end -= 1Explanation:
- Modulo Operation:
- The first step is to handle cases where
kis greater than the length of the array. Rotating an array by its length results in the same array, so we calculatek % len(nums)to get the effective number of rotations.
- The first step is to handle cases where
- Reversing the Array:
- The main idea behind this algorithm is that by reversing parts of the array, we can achieve the desired rotation.
- First, reverse the entire array. For example, reversing
[1, 2, 3, 4, 5, 6, 7]gives[7, 6, 5, 4, 3, 2, 1]. - Then, reverse the first
kelements. Continuing the example, reversing the first three elements gives[5, 6, 7, 4, 3, 2, 1]. - Finally, reverse the remaining elements. Reversing the last four elements gives
[5, 6, 7, 1, 2, 3, 4], which is the desired result.
- In-place Rotation:
- The solution uses a helper function
reverseto reverse elements in-place between two indicesstartandend. This is done by swapping the elements at the two indices and moving the pointers towards the center.
- The solution uses a helper function
- Time and Space Complexity:
- Time Complexity: O(n), where
nis the number of elements innums. Each element is swapped a constant number of times (once for each of the three reversals). - Space Complexity: O(1), since the reversal operations are done in-place without using extra space.
- Time Complexity: O(n), where
Solution in Javascript
JavaScript
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
var rotate = function(nums, k) {
// Step 1: Handle cases where k is greater than the length of the array
// Using modulo operator to get the effective rotation
k = k % nums.length;
// Step 2: Reverse the entire array
reverse(nums, 0, nums.length - 1);
// Step 3: Reverse the first k elements
reverse(nums, 0, k - 1);
// Step 4: Reverse the remaining elements
reverse(nums, k, nums.length - 1);
};
/**
* Helper function to reverse a portion of the array in-place
* @param {number[]} nums - The array to be reversed
* @param {number} start - Starting index of the portion to reverse
* @param {number} end - Ending index of the portion to reverse
* @return {void}
*/
function reverse(nums, start, end) {
// Swap the elements at start and end indices until they meet in the middle
while (start < end) {
// Swap elements at start and end
let temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
// Move pointers towards the center
start++;
end--;
}
}Solution in Java
Java
class Solution {
public void rotate(int[] nums, int k) {
// Step 1: Handle cases where k is greater than the length of the array
// Using modulo operator to get the effective rotation
k = k % nums.length;
// Step 2: Reverse the entire array
reverse(nums, 0, nums.length - 1);
// Step 3: Reverse the first k elements
reverse(nums, 0, k - 1);
// Step 4: Reverse the remaining elements
reverse(nums, k, nums.length - 1);
}
/**
* Helper method to reverse a portion of the array in-place.
* @param nums - The array to be reversed.
* @param start - Starting index of the portion to reverse.
* @param end - Ending index of the portion to reverse.
*/
private void reverse(int[] nums, int start, int end) {
// Swap the elements at start and end indices until they meet in the middle
while (start < end) {
// Swap elements at start and end
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
// Move pointers towards the center
start++;
end--;
}
}
}Solution in C#
C#
class Solution {
public void Rotate(int[] nums, int k) {
// Step 1: Handle cases where k is greater than the length of the array
// Using modulo operator to get the effective rotation
k = k % nums.Length;
// Step 2: Reverse the entire array
Reverse(nums, 0, nums.Length - 1);
// Step 3: Reverse the first k elements
Reverse(nums, 0, k - 1);
// Step 4: Reverse the remaining elements
Reverse(nums, k, nums.Length - 1);
}
/**
* Helper method to reverse a portion of the array in-place.
* @param nums - The array to be reversed.
* @param start - Starting index of the portion to reverse.
* @param end - Ending index of the portion to reverse.
*/
private void Reverse(int[] nums, int start, int end) {
// Swap the elements at start and end indices until they meet in the middle
while (start < end) {
// Swap elements at start and end
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
// Move pointers towards the center
start++;
end--;
}
}
}