The problem Rotate Array on LeetCode is about rotating an array to the right by a given number of steps. The task is to modify the given array in-place (without using an extra array) and perform the rotation.
Problem Statement: Given an array nums[] and an integer k, rotate the array to the right by k steps.
For example, given the input nums = [1, 2, 3, 4, 5, 6, 7] and k = 3, the modified array should be [5, 6, 7, 1, 2, 3, 4].
There are different ways to approach this problem, but one of the most common ones is to use a reverse technique. This involves reversing the whole array, then reversing the first k elements, and then reversing the remaining elements. This way, you can achieve the rotation in O(n) time and O(1) space.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size(); // get the size of the array
k = k % n; // handle the case when k is larger than n
reverse(nums.begin(), nums.end()); // reverse the whole array
reverse(nums.begin(), nums.begin() + k); // reverse the first k elements
reverse(nums.begin() + k, nums.end()); // reverse the remaining elements
}
};The line k = k % n; is used to handle cases where the value of k is greater than or equal to the length of the array n. It ensures that k remains within the bounds of the array’s length. This is because after n rotations, the array comes back to its original position.
The double reverse technique solves the problem by using the property that reversing a sequence twice will restore it to its original order.
This technique is also useful because it does not require any extra space to store the rotated array. It only modifies the original array in place by swapping elements using a temporary variable. This makes it more efficient than other methods that may require copying or shifting elements in a new array.