Rotate Array — Triple Reverse O(1) Space Deep Dive (Definitive Guide) [Microsoft, Amazon, Google]

Problem Statement

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative. The rotation must be in-place with O(1) extra space.

Example 1 — standard rotation:

Input:  nums = [1, 2, 3, 4, 5, 6, 7], k = 3
Output: [5, 6, 7, 1, 2, 3, 4]
Reason: Rotating right by 1: [7, 1, 2, 3, 4, 5, 6]
        Rotating right by 2: [6, 7, 1, 2, 3, 4, 5]
        Rotating right by 3: [5, 6, 7, 1, 2, 3, 4]

Example 2 — k larger than array length:

Input:  nums = [-1, -100, 3, 99], k = 2
Output: [3, 99, -1, -100]
Reason: k = 2, n = 4. Rotating right twice moves the last 2 elements to the front.
        Note: k = 6 would give the same result since 6 % 4 = 2.

Constraints: 1 <= nums.length <= 10^5, -2^31 <= nums[i] <= 2^31 - 1, 0 <= k <= 10^5

Note: k can be greater than n. This is not a special case — it is a deliberately planted trap.

• Why This Problem Matters
• Three Approaches
• Approach 1 — Extra Array: O(n) Time, O(n) Space
• Approach 2 — Cyclic Replacement: O(n) Time, O(1) Space
• Approach 3 — Triple Reverse: O(n) Time, O(1) Space
• The Reverse Trick Deep Dive
• Why Does It Work?
• The Core Insight
• Index Math Verification
• Handling k > n
• Visual Dry Run
• Common Mistakes
• Mistake 1 — Not applying k % n
• Mistake 2 — Wrong partition point in the reverse steps
• Mistake 3 — Left rotation vs right rotation confusion
• Mistake 4 — Off-by-one in cyclic replacement
• Solutions
• Python — Approach 1: Extra Array
• Python — Approach 2: Cyclic Replacement
• Python — Approach 3: Triple Reverse (Optimal)
• JavaScript — Approach 1: Extra Array
• JavaScript — Approach 2: Cyclic Replacement
• JavaScript — Approach 3: Triple Reverse (Optimal)
• Complexity Analysis
• Follow-up Questions
• Left Rotation by k
• Rotate String — LeetCode 796
• Rotate Image — LeetCode 48
• This Pattern Solves
• Key Takeaway

Why This Problem Matters

LeetCode 189 is on Blind 75 and NeetCode 150 for a reason that has nothing to do with difficulty rating. The naive solution — allocate a new array, copy everything to its rotated position — is something every programmer writes in their first month. It is correct, it is O(n) time, and it is O(n) space. The interviewer nods politely and then asks: "Can you do it in O(1) space?"

That is where the problem earns its spot. To achieve O(1) space, you need to discover one of two non-obvious tricks: the cyclic replacement algorithm or the triple-reverse algorithm. Both work by cleverly permuting elements in-place without ever needing a full auxiliary copy. Neither is immediately obvious from the problem description, which is exactly why this problem appears at Microsoft, Amazon, and Google.

The triple-reverse trick, in particular, is a piece of algorithmic elegance that shocks most developers the first time they see it. "You reverse the whole array three times and somehow end up with a right rotation?" Yes. And the reason why it works is worth understanding deeply, because the same reversal pattern reappears in Rotate String (LC 796), Rotate Image (LC 48), and a family of circular-buffer problems.

Understanding all three approaches — extra array, cyclic replacement, and triple reverse — is what separates a candidate who memorized a solution from one who understands the problem space. Interviewers at senior levels routinely ask you to derive the approach from scratch rather than recall it.

Three Approaches

Approach 1 — Extra Array: O(n) Time, O(n) Space

The conceptually simplest solution: allocate a second array and place each element at its correct rotated position directly.

For a right rotation by k, the element currently at index i should land at index (i + k) % n.

Algorithm:
  new_array = array of size n
  for i in range(n):
      new_array[(i + k) % n] = nums[i]
  copy new_array back into nums

This is crystal-clear, handles all edge cases automatically (including k > n via the modulo), and runs in O(n) time with a single pass. The only cost is the O(n) auxiliary array, which violates the in-place constraint.

When to mention it: Always state this approach first, explain its correctness briefly, then pivot to O(1) space alternatives. It demonstrates you can reason from first principles before optimizing.

Approach 2 — Cyclic Replacement: O(n) Time, O(1) Space

This approach exploits the fact that rotating right by k creates a permutation where each element at index i belongs at index (i + k) % n. Instead of using a second array, we can "chase" each element to its destination and cascade the displacements.

Start at index 0. Save nums[0].
Move nums[0] to its target position (0 + k) % n, saving whatever was there.
Move that saved element to its target, saving whatever was displaced.
Continue until we return to index 0.
If that cycle did not touch all n elements, start a new cycle from index 1.
Repeat until exactly n elements have been moved.

The subtlety is that cycles can close before all elements are visited. This happens when gcd(n, k) > 1. For example, with n=6 and k=2, the cycle 0→2→4→0 closes after only 3 elements. A second cycle 1→3→5→1 covers the rest. The number of distinct cycles is always gcd(n, k).

Cycle termination condition: Use a counter count starting at 0. Each time an element reaches its final position, increment count. Stop when count == n.

This approach is O(n) time and O(1) space (only a few variables: start, current, prev, count). The implementation is trickier than the reverse trick and is more prone to subtle off-by-one errors around cycle detection — which is why the reverse trick is preferred in interviews.

Approach 3 — Triple Reverse: O(n) Time, O(1) Space

This is the approach that makes candidates say "wait, that actually works?" Three in-place reversals on different slices of the array produce a right rotation by k:

Step 1: Reverse the entire array        → indices [0 .. n-1]
Step 2: Reverse the first k elements    → indices [0 .. k-1]
Step 3: Reverse the remaining elements  → indices [k .. n-1]

The implementation is four lines of code, handles all edge cases via k = k % n, and contains zero tricky index arithmetic beyond knowing where to split. This is the approach to present in interviews when O(1) space is required.

The Reverse Trick Deep Dive

Why Does It Work?

Let the array be A = [a₀, a₁, ..., aₙ₋₁]. A right rotation by k means the desired output is:

[aₙ₋ₖ, aₙ₋ₖ₊₁, ..., aₙ₋₁, a₀, a₁, ..., aₙ₋ₖ₋₁]

In other words, the last k elements come to the front (in their original relative order), and the first n-k elements shift to the back.

Now watch what the three reversals do, denoting the original two segments as:

L = [a₀, a₁, ..., aₙ₋ₖ₋₁]   (first n-k elements, the "left" block)
R = [aₙ₋ₖ, aₙ₋ₖ₊₁, ..., aₙ₋₁]   (last k elements, the "right" block)

So the original array is [L | R].

Step 1 — Reverse all:

Reversing the full array reverses both blocks AND swaps their order:

[L | R]  →  reverse all  →  [R_rev | L_rev]

where R_rev is R in reverse order and L_rev is L in reverse order. The right block came to the front — but both halves are in the wrong internal order.

Step 2 — Reverse the first k elements:

The first k elements are exactly R_rev. Reversing them restores their correct order:

[R_rev | L_rev]  →  reverse [0..k-1]  →  [R | L_rev]

The first k positions are now exactly what we want.

Step 3 — Reverse the last n-k elements:

The remaining elements are L_rev. Reversing them restores the correct order of the left block:

[R | L_rev]  →  reverse [k..n-1]  →  [R | L]

Which is [aₙ₋ₖ, aₙ₋ₖ₊₁, ..., aₙ₋₁, a₀, a₁, ..., aₙ₋ₖ₋₁] — a perfect right rotation by k.

The Core Insight

Reversing a block inverts its order. Reversing the entire array moves the right block to the front but inverts everything. The two subsequent reversals of each half "un-invert" each block individually. The order of the two blocks was set by step 1; steps 2 and 3 repair the internal ordering of each block. Because reversing is its own inverse (reverse(reverse(X)) = X), these three operations compose to produce exactly the right rotation.

Index Math Verification

For an element originally at index i:

• If i is in the left block (0 ≤ i < n-k), after step 1 it lands at index n - 1 - i. After step 3 (reversing indices k through n-1), it lands at k + (n - 1 - k) - (n - 1 - i) = i + k. This is the correct rotated position (i + k) % n for elements in the left block (since i + k < n).
• If i is in the right block (n-k ≤ i < n), after step 1 it lands at index n - 1 - i. After step 2 (reversing indices 0 through k-1), it lands at k - 1 - (n - 1 - i) = i - (n - k) = i + k - n. This equals (i + k) % n since i + k ≥ n. Correct.

Every element ends up at exactly (i + k) % n. The triple-reverse is not a trick — it is a deterministic permutation that implements the rotation bijection.

Handling k > n

This is the most common trap in the problem, and it is placed in the constraints deliberately: 0 <= k <= 10^5 while nums.length can be as small as 1.

Without normalization:

If k = 7 and n = 7, rotating right by 7 steps returns the array to its original state. If your code executes three reversals with k = 7 on a 7-element array, it reverses [0..6] (entire array), then reverses [0..6] again (same thing), then reverses an empty slice [7..6] — and you end up with the original array fully reversed. Wrong.

Similarly, if k = 10 and n = 7, a rotation by 10 is identical to a rotation by 3 (since 10 = 7 + 3, and a full rotation brings you back). Without k = k % n, the algorithm slices at position 10, which is out of bounds.

Always normalize first:

k = k % n
if k == 0:
    return  # no rotation needed — k was a multiple of n

The if k == 0 guard is not strictly necessary (the three reversals of a slice of length 0 or n are no-ops), but making it explicit shows the interviewer you understand the edge case.

What k % n handles:

Visual Dry Run

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

Normalize: k = 3 % 7 = 3. n = 7.

We split the work into: left block L = [1, 2, 3, 4] (indices 0..3), right block R = [5, 6, 7] (indices 4..6).

Before anything:

Index:  0  1  2  3  4  5  6
Array: [1, 2, 3, 4, 5, 6, 7]
        ←——— L ———→  ←— R —→

Step 1 — Reverse entire array [0..6]:

[1, 2, 3, 4, 5, 6, 7]
        ↕ swap(0,6)
[7, 2, 3, 4, 5, 6, 1]
        ↕ swap(1,5)
[7, 6, 3, 4, 5, 2, 1]
        ↕ swap(2,4)
[7, 6, 5, 4, 3, 2, 1]
        ↕ index 3 is middle — stays

Result: [7, 6, 5, 4, 3, 2, 1]
         ←— R_rev ——→  ←— L_rev —→

The right block (5, 6, 7) is now at the front — but reversed to (7, 6, 5). The left block (1, 2, 3, 4) is at the back — but reversed to (4, 3, 2, 1).

Step 2 — Reverse first k=3 elements [0..2]:

[7, 6, 5, 4, 3, 2, 1]
 ↕ swap(0,2)
[5, 6, 7, 4, 3, 2, 1]
   ↕ index 1 is middle of [0..2] — stays

Result: [5, 6, 7, 4, 3, 2, 1]
         ←R→  ←———— L_rev ————→

The right block is now correctly [5, 6, 7] at the front.

Step 3 — Reverse remaining elements [3..6]:

[5, 6, 7, 4, 3, 2, 1]
          ↕ swap(3,6)
[5, 6, 7, 1, 3, 2, 4]
             ↕ swap(4,5)
[5, 6, 7, 1, 2, 3, 4]
                ↕ index 5 is middle of [3..6] — stays

Result: [5, 6, 7, 1, 2, 3, 4]  ✓
         ←R→  ←——— L ————→

The left block is now correctly [1, 2, 3, 4] at the back. The array is rotated right by 3. Exactly what we wanted.

Common Mistakes

Mistake 1 — Not applying k % n

The single most frequent source of wrong answers and runtime errors. If k = 7 and n = 7, naively passing k=7 to the reverse step causes you to reverse a slice of size 7 starting at index 7 — which is out of bounds in most implementations, or silently produces a wrong answer.

Fix: Always write k = k % n as the very first line, before any other logic.

# Wrong:
def rotate(nums, k):
    n = len(nums)
    nums.reverse()           # ok
    nums[:k] = nums[:k][::-1]  # if k=14 and n=7: slice beyond end

# Correct:
def rotate(nums, k):
    n = len(nums)
    k %= n                   # normalize first, always
    if k == 0: return
    nums.reverse()
    nums[:k] = nums[:k][::-1]
    nums[k:] = nums[k:][::-1]

Mistake 2 — Wrong partition point in the reverse steps

The split is at index k after normalization. Step 2 reverses [0..k-1] and step 3 reverses [k..n-1]. A common off-by-one is reversing [0..k] (inclusive of k) or [k+1..n-1] (exclusive of k). Both produce a subtly wrong result that passes some test cases.

Mnemonic: After the full reversal, the first k positions hold the elements that should be at the front. Reverse exactly those k positions (indices 0 to k-1, a slice of length k), then reverse everything else.

Mistake 3 — Left rotation vs right rotation confusion

The problem asks for right rotation. A right rotation by k moves the last k elements to the front. A left rotation by k moves the first k elements to the back.

For a right rotation: reverse all → reverse first k → reverse last n-k.

For a left rotation by k: that is equivalent to a right rotation by n - k. Or, swap the order: reverse first k → reverse last n-k → reverse all.

Remembering which is which: "right rotation makes the right side (tail) go to the front." After step 1 (reverse all), the tail is at the front but inverted. Step 2 fixes the tail. Step 3 fixes the head.

Mistake 4 — Off-by-one in cyclic replacement

When implementing cyclic replacement, a common bug is checking cycle closure by comparing current back to start using equality (current == start), but starting current at start before the first move rather than after. This causes the loop to exit immediately on the first check.

The cycle should advance current first, then check. Track total moves with a separate count variable rather than relying purely on cycle detection.

Solutions

Python — Approach 1: Extra Array

from typing import List

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """Rotate right by k using an auxiliary array. O(n) time, O(n) space."""
        n = len(nums)
        k %= n
        # Each element at index i lands at index (i + k) % n in the rotated array
        rotated = [0] * n
        for i in range(n):
            rotated[(i + k) % n] = nums[i]
        # Copy result back into nums in-place (required by problem)
        nums[:] = rotated

Python — Approach 2: Cyclic Replacement

from typing import List
from math import gcd

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """Rotate right by k using cyclic replacement. O(n) time, O(1) space."""
        n = len(nums)
        k %= n
        if k == 0:
            return

        count = 0  # total elements placed in their correct rotated position
        start = 0  # starting index of the current cycle

        while count < n:
            current = start
            prev = nums[start]  # save the element we are about to displace

            while True:
                next_idx = (current + k) % n  # destination of current element
                temp = nums[next_idx]          # save element being displaced
                nums[next_idx] = prev          # place current element at destination
                prev = temp                    # the displaced element becomes "current"
                current = next_idx
                count += 1

                # Cycle complete when we return to the starting index of this cycle
                if current == start:
                    break

            start += 1  # start a new cycle from the next index

Python — Approach 3: Triple Reverse (Optimal)

from typing import List

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Rotate right by k using the triple-reverse trick.
        O(n) time, O(1) space.

        Proof: A right rotation by k moves the last k elements to the front.
        Step 1: Reverse all → last k elements are now at front, but inverted.
        Step 2: Reverse first k → restores the original order of the last k elements.
        Step 3: Reverse last n-k → restores the original order of the first n-k elements.
        """
        n = len(nums)
        k %= n       # handle k > n and k == 0 correctly
        if k == 0:
            return

        def reverse(left: int, right: int) -> None:
            """Reverse nums[left..right] in place."""
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

        reverse(0, n - 1)   # Step 1: reverse entire array
        reverse(0, k - 1)   # Step 2: reverse first k elements
        reverse(k, n - 1)   # Step 3: reverse remaining n-k elements

JavaScript — Approach 1: Extra Array

/**
 * Rotate right by k using an auxiliary array.
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
function rotate(nums, k) {
    const n = nums.length;
    k %= n;  // normalize: handles k > n

    // Build the rotated array: element at i goes to position (i + k) % n
    const rotated = new Array(n);
    for (let i = 0; i < n; i++) {
        rotated[(i + k) % n] = nums[i];
    }

    // Copy back into nums in-place
    for (let i = 0; i < n; i++) {
        nums[i] = rotated[i];
    }
}

JavaScript — Approach 2: Cyclic Replacement

/**
 * Rotate right by k using cyclic replacement.
 * O(n) time, O(1) space. Number of distinct cycles = gcd(n, k).
 * @param {number[]} nums
 * @param {number} k
 * @return {void}
 */
function rotate(nums, k) {
    const n = nums.length;
    k %= n;
    if (k === 0) return;

    let count = 0;  // number of elements placed correctly
    let start = 0;  // starting index of current cycle

    while (count < n) {
        let current = start;
        let prev = nums[start];  // element to be placed

        do {
            const nextIdx = (current + k) % n;
            const temp = nums[nextIdx];   // displaced element
            nums[nextIdx] = prev;         // place element at destination
            prev = temp;                  // displaced element becomes the next to place
            current = nextIdx;
            count++;
        } while (current !== start);  // cycle ends when we return to start

        start++;  // begin next cycle
    }
}

JavaScript — Approach 3: Triple Reverse (Optimal)

/**
 * Rotate right by k using the triple-reverse trick.
 * O(n) time, O(1) space — preferred in interviews.
 * @param {number[]} nums
 * @param {number} k
 * @return {void}
 */
function rotate(nums, k) {
    const n = nums.length;
    k %= n;      // critical: normalize k before any reversal
    if (k === 0) return;

    // Helper: reverse nums[left..right] in place
    const reverse = (left, right) => {
        while (left < right) {
            [nums[left], nums[right]] = [nums[right], nums[left]];
            left++;
            right--;
        }
    };

    reverse(0, n - 1);   // Step 1: reverse entire array
    reverse(0, k - 1);   // Step 2: reverse first k elements (the "right block")
    reverse(k, n - 1);   // Step 3: reverse last n-k elements (the "left block")
}

Complexity Analysis

All three approaches run in O(n) time. The distinguishing factor is space. For most interview purposes, triple reverse is preferred over cyclic replacement because the implementation is simpler and less error-prone. Both are correct O(1)-space solutions.

The reversal helper itself runs in O(r - l + 1) time for a slice of length r - l + 1. Over the three calls:

• Step 1: O(n) — full array
• Step 2: O(k) — first k elements
• Step 3: O(n - k) — last n-k elements

Total: O(n + k + (n - k)) = O(2n) = O(n).

Follow-up Questions

Left Rotation by k

To rotate left by k (move first k elements to the back), two equivalent options:

1. Treat it as a right rotation by n - k: call rotate(nums, n - k).
2. Reverse the order of the three steps: reverse first k → reverse last n-k → reverse all.

Option 1 is simpler and reuses the same code. Option 2 demonstrates understanding of why the algorithm works.

Rotate String — LeetCode 796

Problem: Given strings s and goal, return true if goal is a rotation of s.

Key insight: If len(s) != len(goal), impossible. Otherwise, every rotation of s appears as a substring of s + s. So the answer is: goal in (s + s).

def rotateString(s: str, goal: str) -> bool:
    return len(s) == len(goal) and goal in (s + s)

Connection to LC 189: The rotation structure is identical — you are asking whether goal is reachable by applying the rotate-right operation some number of times. The s + s trick is the string analogue of the circular index arithmetic (i + k) % n. The substring check replaces the element-by-element comparison.

Rotate Image — LeetCode 48

Problem: Rotate an n×n matrix 90 degrees clockwise in-place.

Algorithm: Transpose the matrix (swap matrix[i][j] with matrix[j][i]), then reverse each row.

def rotate(matrix):
    n = len(matrix)
    # Step 1: Transpose — swap across main diagonal
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    # Step 2: Reverse each row — the reversal trick applied row-by-row
    for row in matrix:
        row.reverse()

Connection to LC 189: Step 2 is a direct application of the reversal trick — each row is independently reversed in-place. More fundamentally, a 90-degree clockwise rotation of a matrix is a combination of a reflection (transpose) and a reversal (row flip), mirroring exactly how LC 189's triple reverse combines reflections of different array segments. The underlying algebraic structure is the same: compose involutions (operations that are their own inverse) to produce a desired permutation.

This Pattern Solves

The reversal trick — using an operation that is its own inverse (reversing a segment) to compose a non-trivial permutation — appears across many problems:

The unifying theme: reversals are composable. Because reverse(reverse(X)) = X, reversals are involutions, and any permutation can be decomposed into a product of reversals. The triple-reverse for rotation is one specific such decomposition, chosen because it maps naturally to contiguous subarray operations.

Key Takeaway

Rotate Array is an ideal interview problem precisely because its naive solution (O(n) extra space) is obvious, and its optimal solution (O(1) space via triple reverse) requires a genuine insight. The triple-reverse trick works because reversing the full array repositions the two blocks at the cost of inverting each one, and the two subsequent partial reversals undo those inversions — leaving every element at exactly the right rotated index (i + k) % n. Master this one pattern and you will recognize its fingerprint in Rotate Image, Reverse Words in a String, and circular-buffer problems immediately. Always normalize k = k % n before anything else — this single line prevents the most common category of wrong answers on this problem.