189. Rotate Array

Time: O(n)

Space: O(1)

Intuition

Rotating right by k means the last k elements move to the front and the first n-k elements shift right. Observe: if you reverse the entire array, then independently reverse the first k elements and the last n-k elements, you get exactly the rotated result. Three reverses, no extra array.

Algorithm

1Reduce k = k % n to handle rotations larger than the array.
2Reverse the entire array.
3Reverse the first k elements (indices 0 to k-1).
4Reverse the remaining n-k elements (indices k to n-1).

Example Walkthrough

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

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

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

Common Pitfalls

•Reduce k mod n first - otherwise k=7 on a 7-element array does nothing but the naive reversal would still run.
•k = 0 after reduction means no rotation is needed; the three-reversal still works (each reverse is a no-op or reverses then re-reverses the same range).

189.cs

// Approach: Three-reversal trick — rotating right by k is equivalent to three in-place reversals.
// First reduce k modulo n to handle rotations larger than the array length.
// Step 1: reverse the last k elements [n-k .. n-1] into their rotated positions.
// Step 2: reverse the first n-k elements [0 .. n-k-1].
// Step 3: reverse the entire array to combine both reversed halves into the final order.
// Achieves O(1) extra space — no auxiliary array or extra memory needed.
// Time: O(n) Space: O(1)

public class Solution
{
    public void Rotate(int[] nums, int k)
    {
        int n = nums.Length;
        k = k % n;

        Reverse(nums, (n - k), n - 1);
        Reverse(nums, 0, n - k - 1);
        Reverse(nums, 0, n - 1);
    }

    private void Reverse(int[] nums, int start, int end)
    {
        while (start < end)
        {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

Was this solution helpful?