Rotate Array
Given an integer array nums, 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]
Constraints:
- 1 <= nums.length <= 105
- -231 <= nums[i] <= 231 – 1
- 0 <= k <= 105
Step 1 :- Template and Algorithm Implementation
There are two types of two pointer templates.
1). Opposite direction two pointer template
2). Same direction two pointer template
Based on our analysis of the Rotate Array problem statement, this is a non-target-based problem where we need to rotate the elements of an array by k positions. Therefore, we will use the base structure of the opposite direction pointers template.
As observed in the slides, the template alone is not sufficient to solve this problem. Therefore, it must be combined with the following algorithmic steps to arrive at a correct solution.
1). Reverse the entire array to bring the last k elements to the front in reversed order.
2). Reverse the first k elements to restore their original order.
3). Reverse the remaining part of the array (from index k to end) to restore its order as well.
class Solution {
public void rotate(int[] nums, int k) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
//code
left++;
right--;
}
}
}Step 2 : – Reverse the whole array
In this step, we reverse all the elements of the array from the left index to the right index. This operation completely flips the array — the last element moves to the first position, and the first element moves to the last.
Since we’ll be performing the reverse operation multiple times in the upcoming steps, we create a separate method to handle the swapping of numbers. This improves code reusability and readability.
class Solution {
public void rotate(int[] nums, int k) {
int left = 0;
int right = nums.length - 1;
// Step 1: Reverse the whole array
reverse(nums, left, right);
}
private void reverse(int[] arr, int left, int right) {
while (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
}Step 3 : – Reverse first k elements
After the entire array has been reversed, the first k elements now represent the elements that should appear at the start of the rotated array, but they are still in reverse order.
So in this step, we reverse only the first k elements (from left index to k - 1) to restore their correct order within the rotated section.
class Solution {
public void rotate(int[] nums, int k) {
int left = 0;
int right = nums.length - 1;
// Step 1: Reverse the whole array
reverse(nums, left, right);
// Step 2: Reverse first k elements
reverse(nums, 0, k - 1);
}
private void reverse(int[] arr, int left, int right) {
while (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
}Step 4 : – Reverse the remaining elements
After fixing the first k elements, the rest of the array (from index k to right index) is still in reverse order.
In this step, we reverse that remaining portion to restore its original sequence, completing the rotation of the array to the right by k positions.
class Solution {
public void rotate(int[] nums, int k) {
int left = 0;
int right = nums.length - 1;
// Step 1: Reverse the whole array
reverse(nums, left, right);
// Step 2: Reverse first k elements
reverse(nums, 0, k - 1);
// Step 3: Reverse the rest
reverse(nums, k, right);
}
private void reverse(int[] arr, int left, int right) {
while (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
}Step 5 : – Handle cases where k is greater than n.
The corner test case nums =[-1] and k =2 fails due to index out of bound exception.
If k is larger than the length of the array (nums.length), rotating the array n times brings it back to its original position.
Therefore, using k %= nums.length ensures that we only perform the effective number of rotations needed, avoiding unnecessary extra rotations.
class Solution {
public void rotate(int[] nums, int k) {
int left = 0;
int right = nums.length - 1;
k %= nums.length; // In case k > nums.length
// Step 1: Reverse the whole array
reverse(nums, left, right);
// Step 2: Reverse first k elements
reverse(nums, 0, k - 1);
// Step 3: Reverse the rest
reverse(nums, k, right);
}
private void reverse(int[] arr, int left, int right) {
while (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
}Final Code : –
class Solution {
public void rotate(int[] nums, int k) {
int left = 0;
int right = nums.length - 1;
k %= nums.length; // In case k > nums.length
// Step 1: Reverse the whole array
reverse(nums, left, right);
// Step 2: Reverse first k elements
reverse(nums, 0, k - 1);
// Step 3: Reverse the rest
reverse(nums, k, right);
}
private void reverse(int[] arr, int left, int right) {
while (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
}