We need to shift every element in the array k positions to the right. Elements that "fall off" the right end wrap around to the beginning.

An important detail: k can be larger than the array length. Rotating an array of length n by n steps brings it back to the original, so we only care about k % n effective rotations. If k = 10 and n = 7, that's the same as rotating by 3.

The problem also asks us to modify the array in-place, which rules out simply creating and returning a new array (though using extra space as an intermediate step is a valid approach worth understanding).

Key Constraints:

For this problem: Given n up to 10^5, we need O(n) or O(n log n). The brute force O(n * k) approach is too slow when k is close to n. This rules out "rotate one step at a time" but keeps single-pass or multi-pass linear approaches on the table.

Intuition

The most natural way to rotate an array is to do exactly what the problem describes: move every element one position to the right, and wrap the last element to the front. Do this k times.

Each single rotation saves the last element, shifts everything right by one, and places the saved element at the beginning. Repeat that k times and you're done.

Algorithm

Example Walkthrough

Code

Every element gets moved k times, one position per rotation. But we already know its final destination is (i + k) % n. All those intermediate shifts are wasted, we could place it directly.

What if we computed each element's final position and placed it there in one step instead of shifting one position at a time?

Intuition

Instead of shifting elements one at a time, what if we figured out where each element ends up and placed it there directly?

When we rotate right by k, each element at index i moves to index (i + k) % n. That modulo handles the wrapping. So we can create a new array, place every element at its correct rotated index, and copy everything back.

Algorithm

Example Walkthrough

Code

We copy every element twice: once into the temp array, once back into nums. The mapping (i + k) % n is correct, but we shouldn't need a full copy of the array to apply it.

Is there a way to rearrange elements into their rotated positions without using any extra array, just by swapping elements within the original array?

Intuition

This is the elegant solution. The idea is based on an observation that feels almost like magic the first time you see it.

Think about what rotation does to an array. With nums = [1, 2, 3, 4, 5, 6, 7] and k = 3, the result is [5, 6, 7, 1, 2, 3, 4]. Notice that the last 3 elements moved to the front, and the first 4 elements shifted to the back.

Now here's the trick: what if we reversed the entire array first?

[1, 2, 3, 4, 5, 6, 7] reversed is [7, 6, 5, 4, 3, 2, 1].

Look at the first 3 elements: [7, 6, 5]. These are the right elements (5, 6, 7), just in the wrong order. Reverse them: [5, 6, 7].

Now look at the remaining elements: [4, 3, 2, 1]. Again, the right elements (1, 2, 3, 4), wrong order. Reverse them: [1, 2, 3, 4].

Put it together: [5, 6, 7, 1, 2, 3, 4]. That's the answer.

Three reversals, no extra space.

Algorithm

Example Walkthrough

Code