Rotate an Array to the Right in O(n) Time and O(1) Extra Space — Learn the Three-Reversal Algorithm Through Varastra's E-Commerce Product Catalog, Understand Every Step, and Discover How to Solve Array Rotation Interview Problems Without Creating Another Array.
The interview insight: You don't need to move every element individually. Reverse the right sections in the right order, and the entire array falls into place.
You can rotate a list without making a copy. You only need to reverse it three times. It sounds like a magic trick, and it works every time.
The problem at Varastra
Varastra is an online store for Indian ethnic wear. Its home page shows a list of featured sarees. Every day, the list rotates by a few places, so a different saree comes first.
Rotating right by k places means every item moves k places to the right. Items that fall off the end come back at the front.
Dev, a developer, builds a new list each day. It works. But Sam, a senior engineer, asks one question in the code review: "How much extra memory does this use?"
The answer is "as much as the list itself." For a small list that is fine. For a very large one, it is not. In an interview, the question comes with a twist: "Can you do it with no extra list?" (The story is made up.)
The easy way: build a copy
Take the last k items and put them in front of the rest.
def rotate_right_copy(a, k):
n = len(a)
if n == 0:
return a
k %= n
return a[-k:] + a[:-k] if k else a[:]
For [1, 2, 3, 4, 5, 6, 7] and k = 3, the result is [5, 6, 7, 1, 2, 3, 4].
The line k %= n matters. Rotating a list of 7 by 10 is the same as rotating it by 3. The % sign gives the remainder, and the remainder is all that counts. It also stops a crash when the list is empty, so the code checks for an empty list first.
This version is clean. Its cost is O(n) time and O(n) extra space, because it builds a new list.
The in-place way: three reversals
Tara, a new intern, finds a trick. Take [1, 2, 3, 4, 5, 6, 7] and rotate right by 3.
- Reverse everything:
[7, 6, 5, 4, 3, 2, 1] - Reverse the first 3 items:
[5, 6, 7, 4, 3, 2, 1] - Reverse the rest:
[5, 6, 7, 1, 2, 3, 4]
The result is right. No extra list was needed.
Why does it work? The first reversal brings the last 3 items to the front. They arrive in the wrong order, backward. The second reversal fixes their order. The first reversal also put the other items in backward order at the back. The third reversal fixes those too.
Now the code. First, a helper that reverses part of a list by swapping from both ends.
def reverse_in_place(a, left, right):
while left < right:
a[left], a[right] = a[right], a[left]
left += 1
right -= 1
Then the rotation uses it three times.
def rotate_right_in_place(a, k):
n = len(a)
if n == 0:
return
k %= n
reverse_in_place(a, 0, n - 1)
reverse_in_place(a, 0, k - 1)
reverse_in_place(a, k, n - 1)
a = [1, 2, 3, 4, 5, 6, 7]
rotate_right_in_place(a, 3)
print(a) # [5, 6, 7, 1, 2, 3, 4]
Each item is swapped about once per reversal, so the time is O(n). The helper only uses a few variables, so the extra space is O(1).
Try it
Call rotate_right_in_place on [1, 2, 3, 4, 5, 6, 7] with k = 0, then k = 7, then k = 10. What do you expect?
k = 0 and k = 7 leave the list as it was. k = 10 gives [5, 6, 7, 1, 2, 3, 4], the same as k = 3. This is k %= n at work.
Test it
Edge cases break rotation code more than normal cases. Tara checks an empty list, one item, k = 0, k equal to the length, and k bigger than the length. Then she compares the two versions on random lists.
import random
for _ in range(300):
arr = list(range(random.randint(0, 12)))
k = random.randint(0, 30)
b = arr[:]
rotate_right_in_place(b, k)
assert b == rotate_right_copy(arr, k)
print("all tests pass")
An honest result: which one is faster?
You might think the in-place version also wins on speed. It does not. Tara times both on 1,000,000 items with k = 250,000.
import time
def best_time(func, *args):
best = None
for _ in range(3):
start = time.perf_counter()
func(*args)
elapsed = time.perf_counter() - start
best = elapsed if best is None else min(best, elapsed)
return best
big = list(range(1_000_000))
print("copy ", round(best_time(rotate_right_copy, big, 250_000), 4))
print("in place", round(best_time(lambda a, k: rotate_right_in_place(a[:], k), big, 250_000), 4))
Pause and predict
Before you read the numbers: the in-place version uses far less memory. Do you expect it to be faster or slower than the copy?
Answer: Slower, in Python. Slices run in fast built-in code. Reversals run plain Python loops.
On the test machine, the copy took about 0.007 seconds. The in-place version took about 0.08 seconds. That is about ten times slower. (The in-place time includes copying the list first, so the test does not damage the original. That copy is a small part of it.)
Why? Python slices run in quick built-in code. The reversal runs plain Python loops, one swap at a time.
Memory tells the other story. Tara measures the peak extra memory on 200,000 items.
import tracemalloc
def peak_bytes(func, *args):
tracemalloc.start()
func(*args)
_, peak = tracemalloc.get_traced_memory()
tracemalloc.stop()
return peak
data = list(range(200_000))
print(peak_bytes(rotate_right_copy, data, 50_000))
print(peak_bytes(rotate_right_in_place, data[:], 50_000))
The copy used about 3.2 million extra bytes at its peak. The in-place version used 156 bytes.
So the reversal wins on space and loses on speed. Big-O says both are O(n) time. The constant factor decided the stopwatch. These numbers were measured on one machine. They will differ on yours.
Which one should you use?
- In real Python code, use the copy. It is simple and fast.
- In an interview that says "in place" or "O(1) extra space", use the three reversals.
- In a language with no fast slices, such as C or Java, the reversal is a normal and fast choice.
Say the trade out loud:
"I will use three reversals to keep extra space at O(1). The time is O(n)."
How to spot this pattern
- The problem says "rotate", "shift cyclically" or "move the last k to the front."
- The problem says "in place" or "without extra space."
- The problem needs the same order inside each part. Reversals can fix the order of a part.
The same three-step idea also works for "rotate left." You only change the reversal order. Try it on paper with the same list. If you can do it by hand, you can do it in an interview.
Takeaway: To rotate in place, reverse everything, then reverse the first k, then reverse the rest. You trade some speed for O(1) extra space.