Run it: Rotate an array by k in code
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 at once — 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. This 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 change requires slice assignment.
Cyclic replacement — O(1) space, moving each element directly to its final position:
Correct, O(1) space, and much 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 by itself 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. This is how "abcdef" becomes "defabc".
A neat related check: is B a rotation of A? Test whether B in A + A. This 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.