Rotate Array — The Triple-Reverse Trick

Rotate Array sounds trivial: shift every element of an array k positions to the right. But the in-place version trips up a lot of candidates because the obvious approach uses extra memory, and the elegant one is one of those tricks that only feels obvious after you have seen it.

The Problem

Given an integer array nums and an integer k, rotate the array to the right by k steps. k can be larger than the array length.

Example: nums = [1,2,3,4,5,6,7], k = 3 becomes [5,6,7,1,2,3,4].

Intuition

The straightforward solution is to allocate a new array and copy each element nums[i] to position (i + k) % n in the new array. That is O(n) time and O(n) space.

For the O(1) extra-space version, the trick is the triple reverse. Reversing a subarray in place uses no extra memory. Three well-chosen reversals produce the rotation:

1. Reverse the entire array.
2. Reverse the first k elements.
3. Reverse the remaining n - k elements.

Why it works: think of the array as two blocks [A][B] where |B| = k. You want [B][A]. Reversing the whole array yields [reverse(B), reverse(A)]. Then reversing each block restores their internal order, leaving [B][A]. The two blocks have been swapped without allocating anything.

Don’t forget k %= n first. If k exceeds n you would otherwise loop multiple times needlessly.

Explanation with Example

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

• Reverse all: [7,6,5,4,3,2,1].
• Reverse first 3: [5,6,7,4,3,2,1].
• Reverse last 4: [5,6,7,1,2,3,4].

Done.

start         [ 1  2  3  4  5  6  7 ]
                            |  k=3  |

reverse all   [ 7  6  5  4  3  2  1 ]
              |  k=3  |

reverse 0..k-1[ 5  6  7 | 4  3  2  1 ]

reverse k..n-1[ 5  6  7 | 1  2  3  4 ]
            ^^^^^^^^^   ^^^^^^^^^^^^
              last k       first n-k
              (rotated)

before:    [    A    |    B    ]      |B| = k

rev all:   [ rev(B)   |  rev(A) ]

rev L,R:   [    B     |    A    ]      blocks swapped

Code

def rotate(nums, k):
    n = len(nums)
    k %= n
    def reverse(l, r):
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1
    reverse(0, n - 1)
    reverse(0, k - 1)
    reverse(k, n - 1)

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[] a, int l, int r) {
        while (l < r) {
            int t = a[l]; a[l] = a[r]; a[r] = t;
            l++; r--;
        }
    }
}

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

Edge Cases

• k == 0: no work. The modulo handles it naturally.
• k == n: also no work after k %= n.
• n == 1: any rotation is a no-op.
• k negative: not in the standard problem, but if it appears, normalize with k = ((k % n) + n) % n.
• Empty array: handle n == 0 first to avoid division by zero in k % n.

Complexity Analysis

• Triple reverse: O(n) time, O(1) extra space. Each element is touched at most twice across the three reversals.
• Extra array: O(n) time, O(n) space.

How to Explain It in an Interview

Mention both the extra-array approach (which works, but uses O(n) memory) and the triple reverse (which works in place). Sketch why the triple reverse works using the block-swap argument. Always state k %= n explicitly, because forgetting it is the bug interviewers expect.

If asked for yet another approach, mention cyclic replacements: start at index 0, place its value at the rotated position, displace the value that was there, and continue until you have moved n elements. The catch is that if gcd(n, k) > 1 you end up in a shorter cycle and need to restart from the next index. The triple-reverse is shorter, easier to prove, and harder to get wrong.

Related Problems

• Rotate Image (transpose plus row reverse)
• Reverse Words in a String
• Reverse Linked List

Wrap up

In-place rotation shows up in ring buffers, circular queues, streaming windows, and image processing kernels. Once you have the triple-reverse trick in your toolkit, you start seeing it everywhere. A clean primitive like “reverse a subarray” combines into surprisingly powerful transformations.