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

Source: https://www.techinterview.org/post/3233459583/right-rotate-an-array-by-k-elements/
Updated: 2026-04-27 · techinterview.org

## 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:

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

- Reverse first k=3: `[5,6,7,4,3,2,1]`

- 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

### What's the expected interview answer?

  Three-reverse trick: O(n) time, O(1) space, in place. Walk through the algorithm with a small example. Mention extra-array as a warm-up. Strong candidates also explain why three-reverse works (full reversal puts the last k elements at the front; two sub-reversals restore order within each segment).

### How do I handle negative k or k larger than n?

  Normalize: `k = k % n` in Python (which always returns non-negative for positive n) or `k = ((k % n) + n) % n` in C/C++/Java where modulus may return negative. The normalized k is in `[0, n)`; algorithms operate on this normalized value.

### Is cyclic replacement worth implementing?

  Generally no, unless the interviewer specifically asks for it. The complexity is the same as three-reverse but the code is harder to write correctly. Three-reverse is preferred in production and interview settings. Mention cyclic replacement as an alternative if you want to demonstrate breadth, then write three-reverse.

### Does this generalize to multi-dimensional arrays?

  Yes, but the operations differ. Rotating a 2D matrix by 90 degrees uses the transpose-then-reverse pattern (LeetCode #48). Rotating by 180 degrees is two 90-degree rotations or reverse-rows-then-reverse-columns. Multi-dimensional rotations are common follow-ups; the underlying intuition (compose simple operations to get complex ones) is the same as the three-reverse trick.

### What's the most common bug in production rotation code?

  Off-by-one in modulus or slice boundaries. The three-reverse pattern avoids most edge cases but still requires correct sub-array indices. Test on edge cases: k = 0, k = n, k = n + 1, empty array, single-element array. Production code should have unit tests for each.

See also: [Longest Palindromic Substring](/post/3233459618/find-longest-palindrome-in-a-string/) • [Remove a Character from a String](/post/3233459622/removing-a-character-from-a-string/) • [Two Sum: Find a Pair in an Array](/post/3233459633/sum-up-a-pair-in-array/)