VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 01: Arrays and strings

Lesson 1.10 of 16 in this moduleFree

Rotate Array

Rotate an array right by k: from k single-step shifts, to a sliced copy, to three in-place reversals with O(1) extra space. Then huge k, read-only access with a virtual index, ring buffers and np.roll.

about 10 min 5 Python examples 2 quick checks

Problem. Rotate nums to the right by k steps, in place.

text
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.

python
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.

python
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.

rotating [1, 2, 3, 4, 5, 6, 7] right by 3: reversing all gives [7, 6, 5, 4, 3, 2, 1], reversing the first 3 gives [5, 6, 7, 4, 3, 2, 1], and reversing the rest gives [5, 6, 7, 1, 2, 3, 4].
Diagram— rotating [1, 2, 3, 4, 5, 6, 7] right by 3: reversing all gives [7, 6, 5, 4, 3, 2, 1], reversing the first 3 gives [5, 6, 7, 4, 3, 2, 1], and reversing the rest gives [5, 6, 7, 1, 2, 3, 4].
python
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?

  1. Reversal sorts the array
  2. 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
  3. It only works when k divides n
  4. It's a coincidence for this example
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

a decision map: copy with slicing when memory is fine, k % n when k can be large, three reversals for O(1) extra, a virtual index when you only read, and np.roll or deque.rotate for libraries.
Diagram— a decision map: copy with slicing when memory is fine, k % n when k can be large, three reversals for O(1) extra, a virtual index when you only read, and np.roll or deque.rotate for libraries.

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.

python
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.

python
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?

  1. A ring buffer: a fixed array and a moving start index, so each append is O(1) and nothing is shifted
  2. A list where you delete the first element each step
  3. Sort the losses each step
  4. np.roll the array each step
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

  1. Why reduce k with k % n, and what edge case does that need?
  2. What do the three reversals do to the blocks A and B?
  3. How many cycles do cyclic replacements form?
  4. How do you read a rotated array without moving data?
  5. What bug does np.roll cause when building lag features?
  6. How do you rotate left by k using a right rotation?
Answers
  1. Rotations repeat every n steps; guard n = 0 so k % n doesn't divide by zero.
  2. Reversing all gives rev(B) rev(A), the right order but each block backwards; reversing each block fixes it.
  3. gcd(n, k).
  4. The value at rotated position i is nums[(i − k) % n]; a ring buffer stores a start index instead of moving data.
  5. It wraps the end of the series into the start, leaking future values into early rows; mask or use a non-wrapping shift.
  6. Rotate right by n − k (after reducing k modulo n).