Rotate Array

MEDIUM✓ CHIP-TIMEDLC #189 — FULL STATEMENT ↗

The drill: Shift every element of an array k positions to the right, wrapping the tail around to the front — done inside the same array, no second array kept around.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array of values and a shift count k arrive together, and the task is to shift every element k positions to the right, with anything pushed off the end wrapping back around to the front.

The rotation has to happen inside the same array — nothing is returned separately, the mutated array itself is the answer.

k can be larger than the array's own length, in which case only its effective shift (k modulo the array length) actually changes anything; a full lap around lands every element back where it started.

EX 01

nums = [1, 2, 3, 4, 5, 6, 7] · k = 3

→ [5, 6, 7, 1, 2, 3, 4]

THE BOARD'S EXAMPLE

EX 02

nums = [-1, -100, 3, 99] · k = 2

→ [3, 99, -1, -100]

NEGATIVES, HALF-LENGTH ROTATION

EX 03

nums = [1] · k = 0

→ [1]

MINIMUM SIZE, NO-OP ROTATION

array length runs from one up to around one hundred thousand
the shift count k can be zero, or larger than the array length
rotation must happen in place, no second array kept alive
values can be negative, zero, or positive

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Copying into a rotated array and pasting it back works, but a second array is alive the whole time. What operation moves every element to its new spot without ever allocating a parallel array?

HINT 2 THE STRUCTURE

Reversing the whole array almost lands every element in its rotated position — just with each of the two halves internally backwards. Reversing those two halves separately fixes the local order back up.

HINT 3 ONE STEP FROM THE ANSWER

Take k mod n first. Reverse the entire array, then reverse the first k elements, then reverse the remaining n−k — three in-place reversals, no extra array.

COACH'S BOARD — THE PATTERN, STEP BY STEP

REVERSE, REVERSE, REVERSEPATTERN · THREE IN-PLACE REVERSALSnums = [1, 2, 3, 4, 5, 6, 7] · k = 3

STEP 1

k = 3 mod 7 = 3. Reverse everything, then reverse the two pieces back into local order.

STEP 1 / 5 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/rotate-array.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n

        def reverse(lo: int, hi: int) -> None:
            while lo < hi:
                nums[lo], nums[hi] = nums[hi], nums[lo]
                lo += 1
                hi -= 1

        reverse(0, n - 1)
        reverse(0, k - 1)
        reverse(k, n - 1)

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 14 LN

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n
        rotated = [0] * n
        for i in range(n):
            rotated[(i + k) % n] = nums[i]
        for i in range(n):
            nums[i] = rotated[i]

TIME O(N)SPACE O(N)PYTHON · TRAINING PACE · 9 LN

class Solution {
    public 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);
    }

    private 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 O(N)SPACE O(1)JAVA · RACE PACE · 19 LN

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        int[] rotated = new int[n];
        for (int i = 0; i < n; i++) {
            rotated[(i + k) % n] = nums[i];
        }
        System.arraycopy(rotated, 0, nums, 0, n);
    }
}

TIME O(N)SPACE O(N)JAVA · TRAINING PACE · 11 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED