Array Rotation (Left and Right)

# Question

Given an integer array $nums$ and a non-negative integer $k$ , rotate the array:

To the Right: $k$ elements from the back move to the front.
To the Left: $k$ elements from the front move to the back.

The operation must be performed in-place with $O(1)$ extra space.

# Solution

# Pattern

The Triple Reversal Algorithm A mathematical property where an array can be divided into two parts $A$ and $B$ . By reversing $A$ , then $B$ , then the entire array $Reverse(A)Reverse(B)$ , we achieve a cyclic shift.

# How to Identify

Requirement for in-place modification of a sequence.
Cyclic shifts or rotations where elements "wrap around."
Constraints demanding $O(1)$ space and $O(n)$ time.

# Description

Step-by-step explanation:

Step 1: Normalize $k$ . Since rotating $n$ times is a null operation, set $k = k \pmod n$ .
Step 2: Partition the Array. - For Right Rotation: Divide at index $n - k$ $n - k$ .
- For Left Rotation: Divide at index $k$ .
Step 3: Reverse the Parts.
- Reverse the first part.
- Reverse the second part.
Step 4: Global Reverse.
- Reverse the entire array from index $0$ to $n - 1$ .

# The Intuition

Think of the array as two separate blocks: $X$ and $Y$ . If you want to move $X$ to the end (Left Rotation), the goal is to transform $[X, Y]$ into $[Y, X]$ .

Reverse $X \rightarrow [X^R, Y]$
Reverse $Y \rightarrow [X^R, Y^R]$
Reverse the whole thing $\rightarrow [(X^R, Y^R)^R] = [Y, X]$

# Complexity

Label	Worst	Average
Time Complexity	$O(n)$	$O(n)$
Space Complexity	$O(1)$	$O(1)$

# Time Complexity

$O(n)$ . Each element is swapped a maximum of two times across the three reversal steps ( $2n$ operations), which simplifies to linear time.

# Space Complexity

$O(1)$ . Only a single temporary variable is used for swapping, regardless of input size.

# Code

class Solution {
    /**
     * Rotates array to the right by k steps.
     * Logic: Reverse (0 to n-k-1), then (n-k to n-1), then (0 to n-1)
     */
    public void rotateRight(int[] nums, int k) {
        if (nums == null || nums.length < 2) return;
        int n = nums.length;
        k %= n;
        if (k == 0) return;
 
        reverse(nums, 0, n - k - 1);
        reverse(nums, n - k, n - 1);
        reverse(nums, 0, n - 1);
    }
 
    /**
     * Rotates array to the left by k steps.
     * Logic: Reverse (0 to k-1), then (k to n-1), then (0 to n-1)
     */
    public void rotateLeft(int[] nums, int k) {
        if (nums == null || nums.length < 2) return;
        int n = nums.length;
        k %= n;
        if (k == 0) return;
 
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 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--;
        }
    }
}

# Caveats

$k=0$ or $k=n$ : Always perform the modulus and check if $k$ is 0 to avoid unnecessary processing.
Empty Arrays: Defensive coding for null or length == 0 is essential for production-grade code.
Integer Overflow: If $k$ is provided as a very large long, casting and modulus must be done carefully.

# Concepts to Think About

Cyclic Buffers: In many real-world applications (like OS kernels), instead of shifting data, we move the "start" pointer in a virtual circular array.
Cache Locality: The reversal algorithm is faster than the "Juggling" algorithm because it accesses memory in a linear, predictable sequence, which modern CPUs optimize via prefetching.
GCD Juggling: Understanding how the Greatest Common Divisor determines the number of cycles in a permutation.
Left vs. Right Rotation: To perform a Right Rotation by k, the logic is slightly different. You would reverse the last k elements, then the first n−k, then the whole. Can you see how the "split point" moves?
The Juggling Algorithm: There is another O(1) space approach using the Greatest Common Divisor (GCD) of n and k. It moves elements in "cycles." While harder to code, it performs fewer total assignments than the Reversal method.
Block Swap Algorithm: This is another O(n) time approach that is very efficient for large k. It works by swapping blocks of size k recursively.
Why Modulo? If n=5 and k=7, rotating 7 times is the same as rotating 2 times (7(mod5)). Always include this to show you understand cyclic properties.

# Logical Follow-up

Question: Can you solve this with $O(1)$ space without using the reversal trick? Solution: Use the Juggling Algorithm. Calculate $g = GCD(n, k)$ . There are $g$ cycles to process. For each cycle, move elements to their target positions $(i + k) \pmod n$ one by one.

Question: How would you rotate a linked list by $k$ ? Solution: Find the $(n-k)^{th}$ node, make the list circular by connecting the tail to the head, set the new head to the $(n-k+1)^{th}$ node, and break the circular connection.