LeetCode 189 – Rotate Array

Rotate Array is the array version of Reverse Words in a String, and it uses the identical trick: three reversals. It is also the problem where forgetting one modulo turns a correct algorithm into an exception, and where the in-place requirement rules out the answer everybody writes first.

The problem

Rotate an array to the right by k steps, in place.

[1,2,3,4,5,6,7], k = 3  -> [5,6,7,1,2,3,4]
[-1,-100,3,99],  k = 2  -> [3,99,-1,-100]
[1,2],           k = 3  -> [2,1]           k EXCEEDS the length
[1],             k = 0  -> [1]
[1,2,3],         k = 3  -> [1,2,3]         a full rotation is a no-op

k can be larger than the array — the problem says so explicitly — and rotating by n returns the array unchanged. Both facts are handled by one line.

k %= n, and why it is not optional

k = 3, n = 2   ->  rotating by 3 is the same as rotating by 1
k = 7, n = 7   ->  the identity

Without the modulo, the reversal version indexes past the end of the array and throws. It is one character of code and it is the difference between passing and crashing on the third example.

Take the modulo before anything else, and note that k % n can be 0, which must leave the array alone rather than reversing it twice into a mess.

Three reversals

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

reverse everything      [7,6,5,4,3,2,1]
reverse the first k     [5,6,7,4,3,2,1]
reverse the rest        [5,6,7,1,2,3,4]   done

Why it works: rotating right by k moves the last k elements to the front, keeping the order within each group. Reversing the whole array puts those k elements at the front — backwards — and puts the rest behind them, also backwards. Reversing each group separately fixes the order without moving either group.

That explanation is worth giving. The three-line version is easy to recall and easy to write in the wrong order, and the reasoning is what tells you which order is right.

Java

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;                    // k may exceed n; a full rotation is the identity

        reverse(nums, 0, n - 1);   // everything
        reverse(nums, 0, k - 1);   // the k that moved to the front
        reverse(nums, k, n - 1);   // the rest
    }

    private void reverse(int[] nums, int lo, int hi) {
        while (lo < hi) {
            int tmp = nums[lo];
            nums[lo++] = nums[hi];
            nums[hi--] = tmp;
        }
    }
}

k = 0 makes the second call reverse(nums, 0, -1), where lo < hi is immediately false and nothing happens — and the third reverses the whole array back. The two outer reversals cancel and the array is unchanged, which is correct. Worth tracing rather than assuming.

The method returns void and mutates. Reassigning nums inside would change nothing for the caller — Java passes the reference by value — which is the same trap as Merge Sorted Array.

Python

class Solution:
    def rotate(self, nums: list[int], k: int) -> None:
        n = len(nums)
        k %= n

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

        reverse(0, n - 1)
        reverse(0, k - 1)
        reverse(k, n - 1)

The Python trap here is different and worse: nums = nums[-k:] + nums[:-k] is correct arithmetic and rebinds a local name, so the caller sees nothing at all. nums[:] = ... mutates in place and does work — mention it, note that it allocates O(n), then write the reversals.

Complexity

Each element is moved exactly twice by the reversals — once in the full pass, once in its group — so the constant is 2 and the whole thing is one pass' worth of work done twice.

The cyclic-replacement alternative

There is an O(n), O(1) solution that moves each element directly to its final position, following the cycle i → (i + k) % n and carrying the displaced value forward. It touches each element once rather than twice.

It also needs care: the number of cycles is gcd(n, k), so you must restart from a new index that many times and count how many elements you have placed. Getting the loop structure right under pressure is genuinely harder than the reversals, for a factor of two.

Mention it, note the gcd, and write the reversals. Knowing why the cycle count is gcd(n, k) is a nice piece of number theory to have ready if pressed.

The pattern

Double reversal keeps appearing: Reverse Words in a String (151) is this same move on words rather than elements. Reverse Words in a String II (186) is the in-place version of that. The general shape — reverse the whole thing, then reverse the pieces back — is the standard way to permute a sequence in blocks without scratch space.

What the interviewer is checking

• k %= n before anything else.
• That k = 0 and k = n leave the array unchanged.
• The three reversals in the right order, with the reason.
• That it mutates rather than returns — especially in Python.
• A single-element array.
• That you can name the cyclic-replacement alternative and why you did not write it.
• That you connect it to the word-reversal problem rather than treating it as new.