Right Rotate an Array by K Elements: Three-Reverse Trick & Variations

Right Rotate an Array by K Elements: Three-Reverse, Cyclic Replacements, and Modulus Tricks

Rotating an array by k positions is a foundational array problem (LeetCode #189) that appears at FAANG, AI labs, and across the broader interview circuit. The naive solution is O(n×k); the elegant solution is the three-reverse trick (O(n) time, O(1) space). Interviewers also expect candidates to handle k larger than n (modulus reduction) and discuss the cyclic-replacement alternative. This guide covers all three standard approaches with working code, edge cases, and the underlying intuition.

Problem Statement

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative. The rotation is in place and modifies the input array.

Examples:

• nums = [1,2,3,4,5,6,7], k = 3 → [5,6,7,1,2,3,4]
• nums = [1,2], k = 3 → [2,1] (k mod n = 1)
• nums = [-1,-100,3,99], k = 2 → [3,99,-1,-100]

Always normalize k = k % n first; rotating by n is a no-op.

Approach 1: Extra Array (O(n) Space)

Allocate a new array; copy each element to its rotated position.

def rotate_extra(nums: list[int], k: int) -> None:
    """O(n) time, O(n) space."""
    n = len(nums)
    if n == 0:
        return
    k %= n
    rotated = [0] * n
    for i in range(n):
        rotated[(i + k) % n] = nums[i]
    nums[:] = rotated  # copy back into input

Trivial but uses O(n) extra space. Acceptable as a warm-up; interviewers will push for in-place.

Approach 2: Three Reverses (Standard Answer)

Reverse the entire array. Reverse the first k elements. Reverse the remaining n-k elements. The result is the original array rotated right by k.

def rotate(nums: list[int], k: int) -> None:
    """O(n) time, O(1) space — three reverses."""
    n = len(nums)
    if n == 0:
        return
    k %= n

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

    reverse(0, n - 1)        # reverse whole array
    reverse(0, k - 1)        # reverse first k
    reverse(k, n - 1)        # reverse rest


# Test
nums = [1,2,3,4,5,6,7]
rotate(nums, 3)
print(nums)  # [5,6,7,1,2,3,4]

Complexity: O(n) time (three linear passes total), O(1) space.

Why three reverses works

Walk through [1,2,3,4,5,6,7] with k=3:

1. Reverse all: [7,6,5,4,3,2,1]
2. Reverse first k=3: [5,6,7,4,3,2,1]
3. Reverse rest (indices 3 to 6): [5,6,7,1,2,3,4]

The full reversal puts the last k elements at the front (in reversed order); the two sub-reversals restore each segment to its original order. Algebraically: if the original is A|B (where B is the last k elements), the result should be B|A. Full reverse gives reversed(B)|reversed(A); reverse-first-k gives B|reversed(A); reverse-rest gives B|A. Done.

Approach 3: Cyclic Replacements

Move each element directly to its target position, displacing the element there. Track when you’ve returned to the start; jump to a new cycle if needed. O(n) time, O(1) space — same complexity as three-reverse but more complex to code correctly.

def rotate_cyclic(nums: list[int], k: int) -> None:
    """O(n) time, O(1) space — cyclic replacements."""
    n = len(nums)
    if n == 0:
        return
    k %= n

    count = 0  # number of elements placed
    start = 0
    while count < n:
        current = start
        prev = nums[start]
        while True:
            next_idx = (current + k) % n
            nums[next_idx], prev = prev, nums[next_idx]
            current = next_idx
            count += 1
            if current == start:
                break
        start += 1

Trade-off: Same time and space as three-reverse but trickier to implement. The number of cycles equals gcd(n, k); if gcd is 1, one cycle covers all elements. Use only if asked specifically; three-reverse is cleaner.

Common Edge Cases

• Empty array. Return immediately; no work needed.
• Single element. Any rotation leaves it unchanged.
• k = 0. No rotation; can return early or let the algorithm no-op naturally.
• k larger than n. k = k % n handles this. Without modulus, the algorithm may do redundant work or behave incorrectly.
• k equal to n. Equivalent to k = 0 after modulus.
• k negative. Some problems allow negative k for left rotation. Handle with k = k % n in Python (Python’s modulus is always non-negative for positive divisor); in other languages, normalize explicitly: k = ((k % n) + n) % n.

Common Variations

Left rotation

Rotate left by k = rotate right by (n – k). Apply the same three-reverse pattern with adjusted indices.

Rotate a string

Same algorithm if the string is mutable. In Python, strings are immutable; convert to list first or use slicing: s[k:] + s[:k].

Rotate a linked list

(LeetCode #61) Different problem. Make the list circular by linking the tail to the head, walk to the new tail position, break the circle.

Find the rotation index of a sorted rotated array

(LeetCode #153, #33) The reverse problem: given a rotated sorted array, find where the rotation happened or search for an element. Binary search variant.

Reverse words in a string

(LeetCode #151) Apply the three-reverse trick character-by-character: reverse the whole string, then reverse each word individually. Same pattern.

Common Mistakes

• Forgetting k = k % n. When k > n, the algorithm may rotate redundantly or fail outright. Always normalize first.
• Using slicing in Python and missing the in-place requirement. nums = nums[-k:] + nums[:-k] creates a new list; the caller’s reference still points to the original. Use nums[:] = ... to modify in place.
• Off-by-one in the three-reverse boundaries. The first reverse is (0, n-1), the second is (0, k-1), the third is (k, n-1). Check these on a small example before implementing.
• Cyclic replacement bugs. Forgetting to track the start of each cycle; missing the gcd cycle count; off-by-one in the displacement loop. The three-reverse approach has none of these bugs and is easier to verify mentally.
• Treating k as the shift instead of the rotation. Right rotation by k means index i goes to (i + k) % n. Some bad implementations use (i - k) % n (left rotation).

Frequently Asked Questions

See also: Longest Palindromic Substring • Remove a Character from a String • Two Sum: Find a Pair in an Array

function rotate(nums, k) {
    const n = nums.length;
    if (n === 0) return;

    // Handle k > n
    k = k % n;
    if (k === 0) return;

    // Helper to reverse portion of array
    function reverse(start, end) {
        while (start < end) {
            [nums[start], nums[end]] = [nums[end], nums[start]];
            start++;
            end--;
        }
    }

    // Step 1: Reverse entire array
    reverse(0, n - 1);

    // Step 2: Reverse first k elements
    reverse(0, k - 1);

    // Step 3: Reverse remaining elements
    reverse(k, n - 1);
}

// Tests
let arr1 = [1, 2, 3, 4, 5];
rotate(arr1, 2);
console.log(arr1);  // [4, 5, 1, 2, 3]

let arr2 = [1, 2, 3];
rotate(arr2, 4);  // k > n, becomes k=1
console.log(arr2);  // [3, 1, 2]

let arr3 = [1];
rotate(arr3, 5);
console.log(arr3);  // [1] (single element)

Original:        [1, 2, 3, 4, 5, 6, 7]

Step 1 - Reverse all:
                 [7, 6, 5, 4, 3, 2, 1]

Step 2 - Reverse first 3:
                 [5, 6, 7, 4, 3, 2, 1]

Step 3 - Reverse last 4:
                 [5, 6, 7, 1, 2, 3, 4]

Result: Last 3 elements moved to front ✓

function rotateWithSpace(nums, k) {
    const n = nums.length;
    k = k % n;

    // Create new array with rotated elements
    const result = new Array(n);

    for (let i = 0; i < n; i++) {
        result[(i + k) % n] = nums[i];
    }

    // Copy back to original
    for (let i = 0; i < n; i++) {
        nums[i] = result[i];
    }
}

function rotateLeft(nums, k) {
    rotate(nums, nums.length - k);
}

let arr = [1, 2, 3, 4, 5];
rotateLeft(arr, 2);
console.log(arr);  // [3, 4, 5, 1, 2]