Array Traversal Tricks

The problem

Your music app has a "shift the queue" feature: the user taps a button and the last k songs jump to the front. The queue has 100,000 tracks. Every tap should feel instant — no spinner, no lag while the phone shuffles a hundred thousand items around.

"Move the last k to the front" is a rotation, and it's one of a small family of moves — reverse, rotate, enumerate subarrays — that show up again and again. Learn the index tricks behind them once and a surprising share of array problems fall over.

A first attempt

The obvious rotation: to move everything right by k, rotate right by one, k times. Each single-step rotation pulls the last element off and shifts the other n − 1 over.

def rotate_one(arr):
    last = arr.pop()      # remove the final element
    arr.insert(0, last)   # put it at the front — shifts everything, O(n)

Do that k times and you've paid O(n × k). Rotate a 100,000-track queue by 50,000 and that's five billion moves. The spinner is back.

The insight

Here's the trick that feels like magic the first time you see it. Reversal composes into rotation. To rotate right by k:

1. reverse the whole array,
2. reverse the first k elements,
3. reverse the rest.

Reversing is a cheap two-pointer sweep, and you do it three times over — still just O(n), with O(1) extra space. No element is ever inserted or shifted one-at-a-time.

How it works

Take [1, 2, 3, 4, 5] and rotate right by k = 2. The answer should be [4, 5, 1, 2, 3].

start:            1 2 3 4 5      rotate right by k=2
reverse all:      5 4 3 2 1
reverse [0..1]:   4 5 3 2 1
reverse [2..4]:   4 5 1 2 3   ✓

The code

The reverse(arr, i, j) helper is the two-pointer sweep from the Strings lesson, reused three times.

def reverse(arr, i, j):
    while i < j:
        arr[i], arr[j] = arr[j], arr[i]
        i += 1
        j -= 1

def rotate_right(arr, k):
    n = len(arr)
    k %= n                       # k larger than n just wraps around
    reverse(arr, 0, n - 1)
    reverse(arr, 0, k - 1)
    reverse(arr, k, n - 1)

function reverse(arr: number[], i: number, j: number): void {
  while (i < j) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
    i++;
    j--;
  }
}

function rotateRight(arr: number[], k: number): void {
  const n = arr.length;
  k %= n;
  reverse(arr, 0, n - 1);
  reverse(arr, 0, k - 1);
  reverse(arr, k, n - 1);
}

void reverse(int[] arr, int i, int j) {
    while (i < j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
        i++;
        j--;
    }
}

void rotateRight(int[] arr, int k) {
    int n = arr.length;
    k %= n;
    reverse(arr, 0, n - 1);
    reverse(arr, 0, k - 1);
    reverse(arr, k, n - 1);
}

void reverse(int *arr, int i, int j) {
    while (i < j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
        i++;
        j--;
    }
}

void rotate_right(int *arr, int n, int k) {
    k %= n;
    reverse(arr, 0, n - 1);
    reverse(arr, 0, k - 1);
    reverse(arr, k, n - 1);
}

#include <vector>
#include <algorithm>
using namespace std;

void rotateRight(vector<int>& arr, int k) {
    int n = (int)arr.size();
    k %= n;
    reverse(arr.begin(), arr.end());          // whole
    reverse(arr.begin(), arr.begin() + k);    // first k
    reverse(arr.begin() + k, arr.end());      // the rest
}

Complexity

That last row is the key mental model for the next lesson: an array of length n has about n²/2 contiguous subarrays, so examining each one can't be faster than O(n²).

When to use it

Practice

Recap

• A tiny set of index tricks — reverse, rotate, subarray enumeration — covers a large slice of array problems.
• Rotation done naively is O(n·k); the three-reversal trick does it in O(n) time and O(1) space.
• An array has ~n²/2 subarrays, so brute-forcing over all of them is O(n²) — a ceiling smarter algorithms aim to beat.