vizlearn

Rotate an array by k

Interview QuestionsBy Updated

Reverse the whole array, then reverse the first k, then reverse the rest. Three passes, every element moved exactly twice, O(1) extra space. The slice version a[-k:] + a[:-k] is one line and allocates a second array.

Overview

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.

Lists & arraysCoding problemMedium

Step through it

What to watch

  • After the first reversal the blocks are in the right places, backwards.
  • Each subsequent reversal fixes one block.
  • Nothing is allocated — every step is in-place swapping.

Say this out loud

"Three reversals: whole thing, first k, then the rest. O(n) time, O(1) space. And k needs to be k % n first, or a k larger than the array breaks it."

Rotate an array by k

Rotate an array right by k positions, in place.

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

Slicing. a[-k:] + a[:-k] is the Pythonic answer, obviously correct, and O(n) extra memory. Give it first, then offer the in-place version.

Cyclic replacement. Follow the cycle of positions, moving each element directly to its destination. It moves every element exactly once rather than twice, but the number of cycles is gcd(n, k), so it needs an outer loop and is much easier to get wrong.

Run it in Python

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.

rotate.pyPython 3
Output
How the code works
  1. k %= nThe first line, and the one that is usually missing. A k larger than the array sends reverse an out-of-range bound — it raises rather than returning something wrong, which the last block demonstrates.
  2. reverse(a, 0, n - 1)Puts the last k elements at the front in one pass — backwards, along with everything else, which the next two reversals correct.
  3. reverse(a, 0, k - 1) then reverse(a, k, n - 1)Each fixes one block. The boundary is exactly k, which is why the modulo has to happen before any of this.
  4. a[-k:] + a[:-k]The version to offer first. It is correct and readable, and it allocates a whole second array — which is the requirement the question is really about.
Change one thing
  • Pass a negative k. Python's % turns it into the equivalent left rotation for free, unlike C.
  • Implement the cyclic-replacement version. Every element moves once instead of twice, and you need gcd(n, k) starting points.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. The three-reversal rotation uses how much extra space?
  2. Why is `k %= n` needed before the reversals?
  3. After reversing the whole array, why reverse each block again?





 Cheat sheet
Rotate an array by k
Reverse the whole array, then reverse the first k, then reverse the rest. Three passes, every element moved exactly twice, O(1) extra space. The slice version a[-k:] + a[:-k] is one line and allocates a second array.
INTERVIEW · vizlearn.in/interview/rotate-an-array.html
More in Interview
InterviewProduct of array except selfInterviewHow does a Python dict work?InterviewWhy must dictionary keys be hashable?InterviewCount things with a dictionary
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact