153. Rotate Array

Rotating right by k means the last k elements jump to the front. Reverse the whole array, then reverse the first k and the remaining n-k separately, and everything lands in the right place — all in O(1) extra space.

Idea

A right rotation by k moves the final k elements to the front while keeping each block's internal order. There is a neat trick that does this in place with no extra array: reverse three times.

Reversing the entire array puts the last k elements at the front but in reversed order (and the first n-k at the back, also reversed). Reversing each of those two blocks individually restores their original order — leaving a perfect rotation.

Algorithm

1. Normalize k = k % n (rotating by n is a no-op; k can exceed n).
2. Reverse the whole array [0 .. n-1].
3. Reverse the first block [0 .. k-1].
4. Reverse the second block [k .. n-1].

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

• k % 7 = 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].

The result [5,6,7,1,2,3,4] is [1..7] rotated right by 3. ✓

Complexity

• Time: O(n) — three linear reversals.
• Space: O(1) — swaps in place, no auxiliary array.

class Solution {
    public int[] 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);
        return nums;
    }

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