Array Rotation In Place
Shifting every element k positions with a temporary array is obvious and costs O(n) memory. Doing it in place with three reversals costs nothing extra and looks like a magic trick until you see the two halves swap position — at which point it becomes the kind of thing you never forget.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
void reverseRange(vector<int>& a, int i, int j) {
while (i < j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++;
j--;
}
}
void rotateRight(vector<int>& a, int k) {
int n = a.size();
if (n == 0) return;
k = k % n;
reverseRange(a, 0, n - 1);
reverseRange(a, 0, k - 1);
reverseRange(a, k, n - 1);
}
int main() {
vector<int> a = {1, 2, 3, 4, 5, 6, 7};
rotateRight(a, 3);
for (int x : a) cout << x << ' ';
return 0;
}Rotates right by k using three in-place reversals; on {1..7} with k = 3 the result is 5 6 7 1 2 3 4.
How it works, step by step
A right rotation is a block swap
Rotating right by k means the last k elements move to the front and the first n-k move behind them. Written as blocks, [A][B] becomes [B][A]. Every rotation algorithm is some way of performing that swap without a buffer.
Reversing the whole array gets the blocks in the right order
Reversing [A][B] gives [reverse(B)][reverse(A)]. The blocks are now in the correct positions — B before A — but each one is internally backwards. That is the only insight the trick needs.
Two more reversals fix the interiors
Reversing the first k elements restores B, and reversing the remaining n-k restores A. Three reversals, each linear, and no extra storage.
k must be reduced modulo n
Rotating by n is the identity, so rotating by k and by k % n are the same operation. Without the modulo, k > n makes reverseRange receive indices outside the array.
Total work is 2n swaps
The full reversal touches n elements and the two partial reversals touch n between them, so about n swaps in total — twice the memory traffic of the buffer version, but with O(1) space. That trade is usually worth it and occasionally is not.
Complexity
Three passes that collectively reverse 2n positions, all in place; the alternative juggling algorithm using GCD cycles does exactly n moves instead of 2n but has far worse cache behaviour, which is why the reversal version is usually faster in practice.
Common bugs
Forgetting k = k % n
Rotating a 7-element array by 10 without the modulo calls reverseRange(a, 0, 9), which reads and writes three elements past the end. The array often survives it because vectors over-allocate, so the bug shows up as corrupted data much later rather than as a crash.
Doing the modulo after taking n from an empty vector
k % n divides by zero when the array is empty. The guard for n == 0 has to come before the modulo, not after. This is the one input nobody tests and the one that takes the process down.
Confusing rotate-right with rotate-left
The same three reversals with k replaced by n - k rotate the other direction. If your output looks correct but shifted the wrong way, you have the direction convention inverted, not a bug in the reversals. Check against a small example by hand before touching the code.
Reversing with i <= j instead of i < j
When the range has odd length, i == j at the midpoint and the element is swapped with itself — harmless. But if you then also decrement and increment past each other, an off-by-one in a hand-rolled loop can swap the same pair twice and undo the reversal. Watching the two indices cross makes it obvious whether the loop stopped at the right moment.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
How do you rotate an array in place?
Reverse the entire array, then reverse the first k elements, then reverse the remaining n-k. The first reversal puts the two blocks in the correct order but internally backwards; the two partial reversals repair them. It uses O(1) extra space and O(n) time.
Why do three reversals rotate an array?
Because reversing a concatenation [A][B] produces [reverse(B)][reverse(A)] — the blocks swap places as a side effect. Since a right rotation by k is exactly the transformation from [A][B] to [B][A], you only need to undo the two internal reversals afterwards.
What happens if k is larger than the array length?
Rotating by n returns the array to its original state, so only k modulo n matters. Without reducing k first, the partial reversals get index bounds outside the array and read or write out of range, which in C++ is undefined behaviour rather than a clean error.
Is the reversal method faster than using a temporary array?
Not usually in raw speed — the buffer version does n reads and n writes, while the reversal version does about 2n swaps. The reversal method wins on memory: it needs no allocation at all, which matters for large arrays or constrained environments.