Generated by Codex with GPT-5.4

Quick facts

• Difficulty: MEDIUM
• Problem: Rotate Array
• Main tags: Array, Math, Two Pointers

What the problem is really asking

The problem gives an array nums and an integer k. The task is to rotate the array to the right by k positions, modifying the original list in place.

Rotating right means each value moves k positions forward, wrapping around to the front when it passes the end. For example, rotating [1, 2, 3, 4, 5, 6, 7] by 3 steps gives [5, 6, 7, 1, 2, 3, 4].

The important details are easy to miss:

• k can be larger than the array length, so only k % len(nums) matters.
• The answer must be written back into nums, not returned as a separate list.
• A direct extra-array solution is simple, but the best interview answer uses O(1) extra space.

The core idea

A right rotation by k splits the array into two blocks:

• A: everything before the last k values
• B: the last k values

The goal is to turn A B into B A.

For [1, 2, 3, 4, 5, 6, 7] and k = 3, the split is:

• A = [1, 2, 3, 4]
• B = [5, 6, 7]

The target is:

• B A = [5, 6, 7, 1, 2, 3, 4]

The clean trick is to use reversals. Reversing the whole array turns A B into reverse(B) reverse(A). Then reversing each block separately restores the inside order of both blocks, producing B A.

How to derive the optimal solution

Start with the obvious formula: the value at index i should move to (i + k) % n. That tells us the rotation is just a remapping of positions.

One solution is to allocate a new array and place each value at its destination. That is correct and runs in O(n) time, but it uses O(n) extra space.

To remove the extra array, look at the rotated result as two blocks. The last k values need to become the prefix, and the first n - k values need to move behind them. Reversal is useful because it can reorder a contiguous block in place using only two pointers.

The three-reversal method is:

1. Normalize k with k %= n.
2. Reverse the whole array.
3. Reverse the first k values.
4. Reverse the remaining n - k values.

For [1, 2, 3, 4, 5, 6, 7] and k = 3:

1. Reverse all values: [7, 6, 5, 4, 3, 2, 1]
2. Reverse the first 3: [5, 6, 7, 4, 3, 2, 1]
3. Reverse the rest: [5, 6, 7, 1, 2, 3, 4]

This is optimal for the in-place version: O(n) time and O(1) extra space.

Python solution

from __future__ import annotations

from typing import MutableSequence


class ArrayRotator:
    """Rotate mutable sequences in place."""

    def rotate_right(self, values: MutableSequence[int], steps: int) -> None:
        """
        Rotate ``values`` to the right by ``steps`` positions in place.

        Time: O(n)
        Extra space: O(1)
        """
        if steps < 0:
            raise ValueError("steps must be non-negative for right rotation.")

        length = len(values)
        if length <= 1:
            return

        normalized_steps = steps % length
        if normalized_steps == 0:
            return

        self._reverse_range(values, 0, length - 1)
        self._reverse_range(values, 0, normalized_steps - 1)
        self._reverse_range(values, normalized_steps, length - 1)

    def _reverse_range(
        self,
        values: MutableSequence[int],
        left_index: int,
        right_index: int,
    ) -> None:
        """Reverse values between two inclusive indices."""
        while left_index < right_index:
            values[left_index], values[right_index] = (
                values[right_index],
                values[left_index],
            )
            left_index += 1
            right_index -= 1


class Solution:
    def rotate(self, nums: list[int], k: int) -> None:
        """LeetCode entry point: mutate nums in place and return None."""
        ArrayRotator().rotate_right(nums, k)

Why this works

After normalizing k, the desired final array is exactly the last k elements followed by the first n - k elements.

If the original array is A B, where B has length k, reversing the whole array gives reverse(B) reverse(A). That puts the two blocks in the correct block order, but each block is internally backward. Reversing the first block restores B, and reversing the second block restores A.

Every element is swapped a constant number of times, so the runtime is O(n). The algorithm only keeps a few index variables, so the extra space is O(1).

Interview follow-ups

What if the interviewer allows an extra array?

The simplest solution creates a new array of the same length. For each index i, place nums[i] at (i + k) % n in the new array. After the pass, copy the new array back into nums.

This approach is often the best starting point because it comes directly from the definition of rotation. It is also hard to get wrong. The tradeoff is space: it runs in O(n) time but uses O(n) extra memory. In interviews, this is a good baseline before improving to the in-place reversal method.

What if the interviewer asks for a left rotation instead?

A left rotation by k is equivalent to a right rotation by n - (k % n). Another way to think about it is that the first k elements move to the end instead of the last k elements moving to the front.

The same reversal pattern still works. Normalize k, reverse the whole array, reverse the first n - k elements, and then reverse the final k elements. Or, more simply in code, convert the request to a right rotation and reuse the same helper. The complexity remains O(n) time and O(1) extra space.

What if the interviewer asks for the cycle replacement solution?

Cycle replacement uses the index formula directly. Starting from some index, move its value to (index + k) % n, keep the displaced value, and continue until the cycle returns to the start. Some rotations form one large cycle, while others form several smaller cycles. The number of cycles is related to gcd(n, k).

This method is also O(n) time and O(1) extra space, but it is easier to write incorrectly because the code must track when a cycle closes and how many values have been moved overall. The reversal solution is usually preferred in interviews because it is shorter, clearer, and less error-prone.

What if k is much larger than the array length?

Only the remainder matters. Rotating an array of length n by exactly n steps returns it to the same state, so rotating by k steps is the same as rotating by k % n steps.

This matters for correctness and efficiency. Without normalization, the algorithm might do unnecessary work or calculate wrong boundaries. With normalization, very large k values are handled in constant time before the main O(n) reversal work starts.

What if the input is empty or has one element?

For an empty array or a single-element array, every rotation leaves the array unchanged. Production code should return immediately for these cases.

LeetCode’s constraints usually avoid an empty nums, but handling it makes the helper safer and avoids division by zero when computing k % len(nums). The early return has no effect on the normal complexity; it simply makes the edge case explicit.