Problem. Rotate nums to the right by k steps, in place.
nums = [1, 2, 3, 4, 5, 6, 7], k = 3 → [5, 6, 7, 1, 2, 3, 4]
nums = [-1, -100, 3, 99], k = 2 → [3, 99, -1, -100]
ML context. Rotations are everywhere in sequence work: shifting a time series to build lagged features,
ring buffers that keep the last N losses or frames, circular padding in convolutions, and data augmentation that
rolls a signal. In NumPy this is np.roll; knowing what it costs (and when you can avoid moving data at all) is the
point of this lesson.
1. Step 1: Clarify
| Question | Answer | Why it matters |
|---|---|---|
| Can k exceed n? | Yes, up to 10⁹ | Rotating by n changes nothing: use k % n |
| In place? | Yes, O(1) extra ideally | Rules out a copy as the final answer |
| n? | Up to 10⁵ | O(n · k) can reach 10¹⁰ |
| Empty array? | Possible | k % 0 would crash: guard it |
2. Step 2: Brute force
Rotate by one step, k times: save the last value, shift everything right, put it at the front.
def rotate_brute(nums, k):
n = len(nums)
if n == 0:
return
for _ in range(k % n):
last = nums[-1]
for i in range(n - 1, 0, -1): # shift right by one: O(n)
nums[i] = nums[i - 1]
nums[0] = last
nums = [1, 2, 3, 4, 5, 6, 7]
rotate_brute(nums, 3)
assert nums == [5, 6, 7, 1, 2, 3, 4]
print("one step at a time works: O(n · k) time, O(1) space")
O(n · k) time. With n = 10⁵ and k = n/2, that's 5 × 10⁹ moves. Already note the first fix, k % n: without it,
k = 10⁹ would mean a billion passes for a result that repeats every n steps.
3. Step 3: Optimise
Optimisation 1: compute each value's destination (O(n) time, O(n) space)
Each element at index i ends up at (i + k) % n. Slicing does it in one go: the last k values, then the rest.
def rotate_copy(nums, k):
n = len(nums)
if n == 0:
return
k %= n
nums[:] = nums[-k:] + nums[:-k] if k else nums[:] # builds a new list: O(n) extra
nums = [1, 2, 3, 4, 5, 6, 7]
rotate_copy(nums, 3)
assert nums == [5, 6, 7, 1, 2, 3, 4]
nums = [1, 2]
rotate_copy(nums, 10**9 + 1)
assert nums == [2, 1]
print("slicing works: O(n) time, O(n) extra space")
O(n) time, but O(n) extra memory. If the constraint is O(1) extra, we need to move values within the array.
Optimisation 2: three reversals (O(n) time, O(1) space)
First principles. Rotating right by k swaps two blocks: A = nums[:n−k] and B = nums[n−k:]; we want B A.
Reversing the whole array gives rev(B) rev(A): the blocks are in the right place, but each is backwards. Reversing
each block again fixes them. Reversal is easy in place: swap from both ends inwards.
import random
def reverse(nums, lo, hi):
while lo < hi:
nums[lo], nums[hi] = nums[hi], nums[lo]
lo += 1
hi -= 1
def rotate(nums, k):
n = len(nums)
if n == 0:
return
k %= n
reverse(nums, 0, n - 1) # A B → rev(B) rev(A)
reverse(nums, 0, k - 1) # fix B
reverse(nums, k, n - 1) # fix A
nums = [1, 2, 3, 4, 5, 6, 7]
rotate(nums, 3)
assert nums == [5, 6, 7, 1, 2, 3, 4]
rng = random.Random(23)
for _ in range(1000):
n = rng.randint(0, 12)
case = list(range(n))
k = rng.randint(0, 50)
want = [case[(i - k) % n] for i in range(n)] if n else []
got = list(case)
rotate(got, k)
assert got == want
print("three reversals: O(n) time, O(1) extra, matches the definition on 1,000 cases")
- Time: each element is swapped about twice: O(n). Space: O(1).
- Edge cases handled: empty array (guard), k = 0 or k = n (k % n = 0 reverses everything twice back), k > n (modulo).
Quick check
Why does reversing the whole array, then each block, rotate it?
Show the answer
B. Rotation swaps blocks A and B; a full reversal puts the blocks in the right order but each one backwards, and reversing each block restores its internal order — rev(A B) = rev(B) rev(A); reversing each part again gives B A.
Another O(1) method: cyclic replacements
Move each value straight to (i + k) % n, carrying the displaced value onwards until the cycle returns to its
start. There are gcd(n, k) such cycles. Also O(n) time, O(1) space, but the cycle bookkeeping is easier to get
wrong. In an interview, mention it and implement the reversals.
4. When the constraints change
Change A: you only need to read the rotated array
Don't move anything. The value at position i of the rotated array is nums[(i − k) % n]. That's O(1) per read and
O(1) to "rotate": just change k. This is exactly how a ring buffer works: a fixed array plus a moving start
index.
class RingBuffer:
"""Keeps the last `size` values; rotation is just moving an index."""
def __init__(self, size):
self.data = [None] * size
self.start = 0
self.count = 0
def append(self, x):
end = (self.start + self.count) % len(self.data)
self.data[end] = x
if self.count < len(self.data):
self.count += 1
else:
self.start = (self.start + 1) % len(self.data) # overwrite the oldest
def items(self):
return [self.data[(self.start + i) % len(self.data)] for i in range(self.count)]
recent_losses = RingBuffer(3)
for loss in [0.9, 0.7, 0.6, 0.55, 0.52]:
recent_losses.append(loss)
assert recent_losses.items() == [0.6, 0.55, 0.52]
print("ring buffer: O(1) per append, no data moved")
Change B: NumPy arrays or deques
np.roll(x, k) and collections.deque.rotate(k) do it for you. Both still cost O(n) (np.roll builds a new
array; a deque's rotate is O(k)), so use them for clarity, not because they're free.
from collections import deque
import numpy as np
x = np.arange(1, 8)
assert np.roll(x, 3).tolist() == [5, 6, 7, 1, 2, 3, 4]
d = deque([1, 2, 3, 4, 5, 6, 7])
d.rotate(3)
assert list(d) == [5, 6, 7, 1, 2, 3, 4]
series = np.array([10.0, 11.0, 12.0, 13.0])
lag1 = np.roll(series, 1)
lag1[0] = np.nan # a lag feature must not wrap around
assert np.isnan(lag1[0]) and lag1[1:].tolist() == [10.0, 11.0, 12.0]
print("np.roll and deque.rotate match; mask the wrapped values for lag features")
The last example is a real ML bug: np.roll wraps, so a lagged feature built with it leaks the end of the series
into the start. Mask the wrapped positions (or use shift in pandas).
Change C: rotate left instead of right
Rotating left by k is rotating right by n − k; or reverse the first k, the rest, then all.
The full table
| If the constraint becomes… | Best approach | Time | Extra space |
|---|---|---|---|
| Memory is fine | Slicing into a copy | O(n) | O(n) |
| In place, O(1) extra | Three reversals | O(n) | O(1) |
| In place, fewest writes | Cyclic replacements (gcd(n, k) cycles) | O(n), each value written once | O(1) |
| k up to 10⁹ | Reduce with k % n first | — | — |
| Only reads needed | Virtual index (i − k) % n |
O(1) per read | O(1) |
| Fixed window of recent items | Ring buffer | O(1) per append | O(size) |
| NumPy / lag features | np.roll + mask the wrapped part |
O(n) | O(n) |
Quick check
You keep the last 1,000 losses during training and add one per step. What's the efficient structure?
Show the answer
A. A ring buffer: a fixed array and a moving start index, so each append is O(1) and nothing is shifted — Deleting from the front or rolling is O(n) per step; moving an index is O(1).
5. Saying it out loud
"First, k %= n, since rotating by n is a no-op. Shifting one step k times is O(n · k); slicing is O(n) but uses O(n) memory. In place, I'll reverse the whole array, then the first k and the last n − k: O(n) time, O(1) space. If we only need to read the rotated array, I wouldn't move anything: index with (i − k) mod n, like a ring buffer."
Check yourself
- Why reduce k with
k % n, and what edge case does that need? - What do the three reversals do to the blocks A and B?
- How many cycles do cyclic replacements form?
- How do you read a rotated array without moving data?
- What bug does
np.rollcause when building lag features? - How do you rotate left by k using a right rotation?
Answers
- Rotations repeat every n steps; guard n = 0 so
k % ndoesn't divide by zero. - Reversing all gives rev(B) rev(A), the right order but each block backwards; reversing each block fixes it.
- gcd(n, k).
- The value at rotated position i is
nums[(i − k) % n]; a ring buffer stores a start index instead of moving data. - It wraps the end of the series into the start, leaking future values into early rows; mask or use a non-wrapping shift.
- Rotate right by
n − k(after reducing k modulo n).