Run it
The three-reversal rotation printed after each step, checked against the slice version for every k from 0 to n, including the values larger than the array.
The three-reversal trick
O(n) time, O(1) space, and three simple loops.
Tracing [1,2,3,4,5,6,7] with k = 3:
| Step | Array |
|---|
| Start | [1,2,3,4,5,6,7] |
| Reverse all | [7,6,5,4,3,2,1] |
| Reverse first 3 | [5,6,7,4,3,2,1] |
| Reverse last 4 | [5,6,7,1,2,3,4] |
Why it works: reversing the whole array puts the last k elements at the front, in reverse order, and the first n−k at the back, also reversed. Reversing each section separately un-reverses them. Every element ends where it should.
Why three reversals work
A right rotation by k moves the last k elements to the front and slides the rest along. Reversing the whole array puts those k at the front immediately — but reversed, and the other block reversed too. Reversing each block separately undoes exactly that.
Total work is 3·n/2 swaps, so O(n) time, and the only storage is a couple of indices.
The modulo, and the empty case
k %= n first. A k larger than the array is a rotation of k % n, and without the modulo the block boundaries go out of range. A k that is a multiple of n leaves the array unchanged, which the modulo also handles for free.
Negative k is a left rotation. Python's % already returns a non-negative result for a positive divisor, so k %= n converts it correctly — a detail worth mentioning because it differs from C.
The alternatives
Slice assignment — the Pythonic answer, O(n) space:
The nums[:] = is important: assigning nums = ... rebinds the local name and leaves the caller's list unchanged. In-place modification requires slice assignment.
Cyclic replacement — O(1) space, moving each element directly to its final position:
Correct, O(1) space, and considerably harder to get right — the outer loop exists because the permutation may consist of several disjoint cycles, and the number of cycles is gcd(n, k).
collections.deque.rotate(k) does it in one call if the container can be a deque, and it is O(k).
| Approach | Time | Space | Clarity |
|---|
| Slice assignment | O(n) | O(n) | Best |
| Three reversals | O(n) | O(1) | Good |
| Cyclic replacement | O(n) | O(1) | Poor |
deque.rotate | O(k) | O(1) | Best, if a deque is allowed |
Edge cases
| Case | Handling |
|---|
k = 0 | No change — return early |
k = n | No change, after k %= n |
k > n | k %= n reduces it |
k negative | Left rotation; convert with k %= n in Python, which handles it |
| Empty array | k %= 0 raises — guard first |
| Single element | No change |
The empty-array case is worth handling explicitly, because % by zero raises ZeroDivisionError and the guard is one line.
Python's % on negatives is helpful here: -3 % 7 is 4, so a negative k automatically becomes the equivalent right rotation. In languages where % follows the sign of the dividend, that needs an explicit adjustment — a good detail to mention.
Rotating left, and by other units
Left rotation by k is right rotation by n - k. Either convert, or reorder the three reversals: reverse the first k, reverse the rest, reverse the whole thing.
Rotating a matrix by 90° is a related classic and uses a similar decomposition: transpose, then reverse each row. Same idea — a rotation expressed as two simpler in-place operations.
Rotating a linked list requires finding the new tail by walking n - k nodes, then relinking. O(n) time, O(1) space, and no reversal needed.
Rotating a string is the same three-reversal algorithm on a character list, which is how "abcdef" becomes "defabc".
A neat related check: is B a rotation of A? Test whether B in A + A, which works because every rotation of A appears as a substring of A doubled.
Where rotation appears in practice
- Circular buffers. Ring buffers in audio, networking and logging are rotation by index arithmetic rather than by moving data — which is the better answer when it is available.
- Round-robin scheduling and load balancing.
- Caesar and rotation ciphers.
- Image and matrix transforms.
- Carousel and slideshow interfaces.
- Rotated sorted array search, the common follow-up problem — binary search on an array that has been rotated by an unknown amount.
The circular-buffer point is the practically important one: if you find yourself rotating an array repeatedly, you probably want an offset variable instead. Keeping a logical start index and computing (i + offset) % n on access is O(1) per rotation and moves no data at all.
What it is testing
Do you normalise k? k %= n is the line most first attempts omit, and k > n is always in the test suite.
Do you get O(1) space? The slice version is correct and allocates; the three-reversal version is the expected improvement.
Do you know nums[:] = versus nums =? A real Python distinction, and rebinding silently fails to modify the caller's list.
Can you explain why three reversals work? Reciting the steps is weaker than explaining that reversing the whole array places the sections correctly but internally backwards.
Do you suggest an offset instead when told rotation happens often? That is the answer a systems-minded interviewer is hoping for.
Recap in one screen
- Normalise with
k %= n first; k can exceed the length, and that is always tested. - Reverse the whole array, then the first k, then the rest — O(n) time, O(1) space.
nums[:] = ... modifies in place; nums = ... only rebinds the local name.- Left rotation by k is right rotation by n−k.
- If rotation is frequent, keep an offset and index modulo n rather than moving data.