A circular log buffer of n slots has to rotate right by k so the newest k lines sit at the front before a dump. The intern allocated a second array and wrote tmp[(i + k) % n] = nums[i]. A few hundred lines were fine. The board then forbade the extra buffer: rotate in the same slots.

Rotate Array asks you to shift every index right by k. An array already gives nums[i] for free. Copying into a second buffer uses that and still allocates n. The in-place answer is not a sliding loop of one-step swaps — that is O(nk) — it is three reverses after k is reduced modulo n.

This is an interview writeup, not a layout lecture. The array post owns slots and indexes. Here rotation is a permutation of those slots, and reverse is the cheap way to apply it without a second copy.

The problem

Given an int[] nums and an int k, rotate the array to the right by k steps: the last k values move to the front, the rest shift right. Mutate nums. k may be larger than n. Prefer O(1) extra space.

nums = [2, 4, 6, 8, 1, 3, 5], k = 3  →  [1, 3, 5, 2, 4, 6, 8]
nums = [9, -2, 4, 0],         k = 2  →  [4, 0, 9, -2]
nums = [8, 1],                k = 5  →  [1, 8]   because 5 % 2 = 1

Note: Right, not left. k %= n before you touch the array. k = 0 after the mod is a no-op. The extra array is correct and the space they usually reject.

Copy into a second array

Each index lands at (i + k) % n in a new buffer, then copy back. Correct. Linear. You paid O(n) extra slots for a permutation the original array can apply with swaps.

void rotateExtra(int[] nums, int k) {
    int n = nums.length;
    k %= n;
    int[] tmp = new int[n];
    for (int i = 0; i < n; i++) {
        tmp[(i + k) % n] = nums[i];
    }
    System.arraycopy(tmp, 0, nums, 0, n);
}

At n = 20 this is a rounding error. The complaint is the extra buffer. Three reverses already answer: the new prefix is the old suffix of length k.

Reverse the whole array, then each half

A right rotate by k puts the last k elements in front, in the same relative order, and the first n - k behind them, also in the same relative order. Reverse is how you move a block without allocating it.

  1. Reverse the whole array. The old suffix is now a prefix, reversed.
  2. Reverse the first k slots. That prefix is in original order.
  3. Reverse the remaining n - k slots. The rest is in original order.
[2, 4, 6, 8, 1, 3, 5]   k = 3

reverse all             [5, 3, 1, 8, 6, 4, 2]
reverse first k         [1, 3, 5, 8, 6, 4, 2]
reverse rest            [1, 3, 5, 2, 4, 6, 8]

The Java is those three calls. reverse(lo, hi) with hi < lo (when k = 0) is a no-op, then the second full reverse undoes the first.

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

void reverse(int[] nums, int lo, int hi) {
    while (lo < hi) {
        int tmp = nums[lo];
        nums[lo] = nums[hi];
        nums[hi] = tmp;
        lo++;
        hi--;
    }
}

Time is O(n) — each index is swapped a constant number of times. Extra space is O(1) — a temp and two indexes. The second array is the same time bill and the space they rejected; say so, then reverse.

Note: Reduce k modulo n first. Without it, reverse bounds walk off the array. One-step rotate in a loop k times is O(nk) and times out the moment k is large. Cycle-follow (i → (i + k) % n, gcd(k, n) cycles) is also O(n) / O(1); it is harder to write under a clock. Reverse is the board answer.

What interviewers usually poke next

  • Left rotate by k. Reverse the first k, reverse the rest, reverse the whole — or right-rotate by n - k. Same three reverses, different cut.
  • Cycle replacement. Follow each cycle until you return. Number of cycles is gcd(k, n). Name it if they ban reverse; do not start from it unless they ask.
  • k > n, k = 0, n = 1. The mod handles all three. n = 1 makes every k a no-op.
  • They allow O(n) extra space. Then the copy is honest and shorter. Say why you still know the reverse, then write the copy if they prefer it.

You are done with this problem when you can reverse [2, 4, 6, 8, 1, 3, 5] three times on a whiteboard for k = 3, and you can say out loud why the extra array is honest extra space, why k %= n comes first, and why a k-step bubble is the wrong linear-looking loop.