Back to solutions

Rotate Array

MediumArrays

Rotate the array to the right by k steps in place.

Open problem
Constraints
  • 1 <= n <= 10^5
  • 0 <= k <= 10^5

Triple reversal

Time O(n)Space O(1)

Rotating right by k is the same as reversing the whole array, then reversing the first k elements and the remaining n-k elements separately. Reduce k modulo n first so large k values are handled. This rearranges in place with O(1) extra space.

Key terms
rotation:
Shifting every element a fixed number of places, wrapping around the ends.
reverse trick:
Three reversals turn the array into its rotation without extra memory.
void rotate(vector<int>& nums, int k) {
    int n = nums.size();
    k %= n;
    reverse(nums.begin(), nums.end());
    reverse(nums.begin(), nums.begin() + k);
    reverse(nums.begin() + k, nums.end());
}
Step by step
  1. Reduce k = k mod n so k is within [0, n).
  2. Reverse the entire array.
  3. Reverse the first k elements, then reverse the remaining n-k elements.
  4. The array is now rotated right by k.