Rotate Array — Missing Modulo Broke Round-Robin

Array rotation is a fundamental operation in circular buffers, round-robin schedulers, job queues, and image processing pipelines. Every OS kernel that rotates a task queue by one slot per tick, and every CDN that rotates a server pool for load balancing, relies on efficient array rotation.

The problem: shift every element k positions to the right, wrapping the tail to the front. The naive approach rotates one step at a time: O(n*k). The optimal approach uses three in-place reversals: O(n) time, O(1) space. The difference matters at scale — rotating a 10000 steps takes 5 billion operations with brute force vs 200,000 with the reversal trick.

The common misconception is that the reversal trick is 'just a trick' with no real-world relevance. In production, circular buffers use the (i + k) % n destination formula for O(1) element access without physically rotating the array. The reversal trick is the physical rotation equivalent when you need the array contents in the rotated0,000-element array by 50, order.

Why Rotating an Array Is Trickier Than It Looks

Rotating an array means shifting its elements by k positions to the right (or left), wrapping around the ends. The core mechanic: each element moves to index (i + k) % n for right rotation, where n is the array length. This modulo operation is the entire game — get it wrong and elements overwrite each other or land in the wrong place.

The naive approach uses O(n) extra space by copying into a new array. The in-place reversal method (reverse entire array, then reverse first k, then reverse rest) runs in O(n) time with O(1) extra space. But the most elegant solution — the round-robin swap — cycles elements through their target positions using a single temporary variable. It works because the permutation decomposes into cycles; the number of cycles equals gcd(n, k).

In production, array rotation appears in buffer management, image pixel shifting, and load-balancing ring structures. The real challenge isn't the rotation itself — it's handling k larger than n, negative k for left rotation, and zero-length arrays. A one-line bug in the modulo logic can silently corrupt data in a circular buffer, making this a deceptively high-stakes operation.

How to Rotate an Array — Three Approaches

Rotating an array right by k steps means the last k elements move to the front. Example: [1,2,3,4,5], k=2 → [4,5,1,2,3].

Approach 1 — Extra array (O(n) time, O(n) space): 1. Create a new array result of same size. 2. For each i: result[(i+k) % n] = arr[i]. 3. Copy result back to arr.

Approach 2 — Reverse trick (O(n) time, O(1) space — optimal): 1. Normalize: k = k % n. 2. Reverse the entire array. 3. Reverse the first k elements. 4. Reverse the remaining n-k elements.

Worked example: [1,2,3,4,5], k=2. Step 1: Reverse all → [5,4,3,2,1]. Step 2: Reverse first 2 → [4,5,3,2,1]. Step 3: Reverse last 3 → [4,5,1,2,3]. Result: [4,5,1,2,3]. Correct.

Why it works: reversing the whole array puts each element in the mirror of its final position. Reversing the two halves individually corrects both halves simultaneously.

package io.thecodeforge.algo;

import java.util.Arrays;

public class ArrayRotationOverview {

    /**
     * Reversal trick: O(n) time, O(1) space.
     * Three in-place reversals achieve full rotation.
     */
    public static void rotateRight(int[] arr, int k) {
        int n = arr.length;
        if (n == 0) return;
        k = k % n;
        if (k == 0) return;

        reverse(arr, 0, n - 1);     // Step 1: reverse entire array
        reverse(arr, 0, k - 1);     // Step 2: reverse first k elements
        reverse(arr, k, n - 1);     // Step 3: reverse remaining elements
    }

    private static void reverse(int[] arr, int from, int to) {
        while (from < to) {
            int temp = arr[from];
            arr[from] = arr[to];
            arr[to] = temp;
            from++;
            to--;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        System.out.println("Before: " + Arrays.toString(arr));
        rotateRight(arr, 3);
        System.out.println("After k=3: " + Arrays.toString(arr)); // [5,6,7,1,2,3,4]

        // Edge case: k >= n
        int[] arr2 = {1, 2, 3, 4, 5};
        rotateRight(arr2, 7); // 7 % 5 = 2
        System.out.println("k=7 (effective k=2): " + Arrays.toString(arr2)); // [4,5,1,2,3]

        // Edge case: k = n (full cycle)
        int[] arr3 = {1, 2, 3};
        rotateRight(arr3, 3); // 3 % 3 = 0, no change
        System.out.println("k=3 (full cycle): " + Arrays.toString(arr3)); // [1,2,3]
    }
}

Brute Force: Rotate One Step at a Time, k Times

The most natural instinct is to rotate the array one position at a time, repeating that k times. For a single right rotation, you save the last element, shift every other element one spot to the right, then place the saved element at index 0. It's easy to reason about because you can watch it happen step by step.

The cost, though, is brutal. For each of the k rotations you're touching every n elements, giving you O(n × k) time. On a 10-element array rotated 3 times that's 30 operations — fine. On a 100,000-element array rotated 50,000 times, that's 5 billion operations. This approach is only acceptable when you know k is tiny and n is small.

There's also a subtle correctness trap here: what if k is larger than n? Rotating a 5-element array by 7 is the same as rotating it by 2 (because after 5 rotations you're back where you started). Always reduce k with k = k % n before you start, or you'll do redundant full loops.

package io.thecodeforge.algo;

import java.util.Arrays;

public class BruteForceRotation {

    /**
     * Rotates the array to the right by 'steps' positions.
     * Strategy: perform a single-step rotation exactly 'steps' times.
     * Time:  O(n * steps)
     * Space: O(1)
     */
    public static void rotateRight(int[] elements, int steps) {
        int length = elements.length;
        if (length == 0) return;

        steps = steps % length;

        for (int round = 0; round < steps; round++) {
            int displaced = elements[length - 1];
            for (int i = length - 1; i > 0; i--) {
                elements[i] = elements[i - 1];
            }
            elements[0] = displaced;
        }
    }

    public static void main(String[] args) {
        int[] schedule = {1, 2, 3, 4, 5, 6, 7};
        System.out.println("Before end up with the original array — correct result, wasted work. If k > n you've done multiple unnecessary full cycles. Always reduce k before the outer loop. This one line separates a beginner's solution from a professional one.

Extra Array Approach: Trade Memory for Clarity

The extra-array approach is the 'obvious' O(n) time solution. You allocate a second array of the same size, calculate each element's destination index with the formula (i + k) % n, copy everything into the right spot, then copy it back. It's clean, readable, and easy to verify by hand.

The destination formula is worth understanding properly. When you rotate right by k, the element currently at index i should land at index (i + k) % n. The modulo handles the wrap-around automatically — no special case needed for elements near the tail.

The trade-off is O(n) extra space. In most application code that's completely acceptable — a few kilobytes for a scheduling array won't move the needle. But in memory-constrained environments (embedded systems, high-frequency trading with tight heap budgets, or the constraints of a LeetCode problem that says 'O(1) space'), this is disqualifying. Knowing when the extra allocation is fine versus when it's a problem is itself a sign of engineering maturity.

package io.thecodeforge.algo;

import java.util.Arrays;

public class ExtraArrayRotation {

    /**
     * Rotates the array to the right by 'steps' positions using a temporary buffer.
     * Time:  O(n)
     * Space: O(n)
     */
    public static void rotateRight(int[] elements, int steps) {
        int length = elements.length;
        if (length == 0) return;

        steps = steps % length;
        if (steps == 0) return;

        int[] buffer = new int[length];

        for (int i = 0; i < length; i++) {
            int destination = (i + steps) % length;
            buffer[destination] = elements[i];
        }

        System.arraycopy(buffer, 0, elements, 0, length);
    }

    public static void main(String[] args) {
        int[] trackIds = {101, 102, 103, 104, 105};
        System.out.println("Before: " + Arrays.toString(trackIds));
        rotateRight(trackIds, 2);
        System.out.println("After k=2: " + Arrays.toString(trackIds));

        // Verify: index 0 (101) -> (0+2)%5=2, index 3 (104) -> (3+2)%5=0 (wraps)
    }
}

The Reversal Trick: O(n) Time, O(1) Space — and Why It Works

This is the approach that separates people who've thought deeply about arrays from those who haven't. It uses three in-place reversals to achieve a full rotation without any extra memory. It feels like magic the first time you see it, but the logic is completely provable.

Here's the insight. A right rotation by k means the last k elements move to the front, and the first n-k elements shift to the back. Think of the array in two chunks: the 'tail' (last k elements) and the 'head' (first n-k elements). If you reverse the entire array, then reverse each chunk independently, you get the rotated result.

Why? Reversing the whole array puts the tail at the front and the head at the back — but both in reversed order. Reversing each section independently corrects the internal order within each chunk. The two reversal errors cancel each other out. It's like turning a sock inside-out twice to clean it: two inversions restore the original orientation, but in a new overall position.

This is the solution LeetCode expects for their 'Rotate Array' problem (problem 189) when they ask for O(1) extra space, and it's the answer that lands job offers.

package io.thecodeforge.algo;

import java.util.Arrays;

public class ReversalTrickRotation {

    /**
     * Rotates the array to the right by 'steps' positions using three reversals.
     * Time:  O(n) — each element is touched at most twice
     * Space: O(1) — in-place swaps
     */
    public static void rotateRight(int[] elements, int steps) {
        int length = elements.length;
        if (length == 0) return;

        steps = steps % length;
        if (steps == 0) return;

        reverse(elements, 0, length - 1);
        reverse(elements, 0, steps - 1);
        reverse(elements, steps, length - 1);
    }

    private static void reverse(int[] elements, int from, int to) {
        while (from < to) {
            int temp = elements[from];
            elements[from] = elements[to];
            elements[to] = temp;
            from++;
            to--;
        }
    }

    public static void main(String[] args) {
        int[] taskQueue = {1, 2, 3, 4, 5, 6, 7};
        System.out.println("Original: " + Arrays.toString(taskQueue));
        rotateRight(taskQueue, 3);
        System.out.println("After k=3: " + Arrays.toString(taskQueue));

        int[] servers = {101, 102, 103, 104, 105};
        rotateRight(servers, 1);
        System.out.println("After k=1: " + Arrays.toString(servers));

        int[] pixels = {255, 128, 64, 32, 16};
        rotateRight(pixels, 12); // 12 % 5 = 2
        System.out.println("k=12 (effective k=2): " + Arrays.toString(pixels));
    }
}

Cyclic Replacement: Move Each Element Directly to Its Final Position

Cyclic replacement is an alternative O(n) time, O(1) space approach. Instead of three reversals, it moves each element directly to its final position in cycles. Start at index 0, move the element to (0 + k) % n, save the displaced element, move it to its final position, and so on until you return to index 0. Then start the next cycle at index 1.

The number of cycles is gcd(n, k) — the greatest common divisor of the array length and the rotation step. Each cycle processes n / gcd(n, k) elements. Total elements processed: gcd(n, k) * (n / gcd(n, k)) = n. O(n) time, O(1) space.

This approach is harder to implement correctly than the reversal trick because you must track when a cycle completes (when you return to the starting index). The reversal trick is preferred in interviews for its simplicity. Cyclic replacement is useful when you need to understand the mathematical structure of the rotation.

package io.thecodeforge.algo;

import java.util.Arrays;

public class CyclicReplacementRotation {

    /**
     * Rotates the array right by k positions using cyclic replacement.
     * Time:  O(n) — each element is moved exactly once
     * Space: O(1) — only one temp variable
     */
    public static void rotateRight(int[] arr, int k) {
        int n = arr.length;
        if (n == 0) return;
        k = k % n;
        if (k == 0) return;

        int count = 0; // total elements moved

        for (int start = 0; count < n; start++) {
            int current = start;
            int prev = arr[start];

            do {
                int next = (current + k) % n;
                int temp = arr[next];
                arr[next] = prev;
                prev = temp;
                current = next;
                count++;
            } while (current != start);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        System.out.println("Before: " + Arrays.toString(arr));
        rotateRight(arr, 3);
        System.out.println("After k=3: " + Arrays.toString(arr));

        // With gcd(n,k) = gcd(6,2) = 2 cycles, each of length 3
        int[] arr2 = {1, 2, 3, 4, 5, 6};
        rotateRight(arr2, 2);
        System.out.println("After k=2: " + Arrays.toString(arr2));
    }
}

The Juggling Algorithm: Don't Confuse Cleverness with Readability

The juggling algorithm is the O(n) time, O(1) space solution that looks like magic until you realize it's just modular arithmetic on steroids. Instead of moving elements one-by-one or using a buffer, you move elements in cycles. You compute the GCD of n and d to figure out how many cycles you need, then rotate each cycle independently.

Why does this work? Because rotating by d is the same as applying a permutation where each element at index i goes to (i - d + n) % n for left rotation. That permutation decomposes into GCD(n, d) disjoint cycles. The juggling algorithm walks each cycle, storing one element in a temporary variable and chasing the chain until you land back where you started.

Here's the catch: it's a nightmare to debug. The logic is tight, the index math is error-prone, and anyone who inherits this code will curse your name. Use it only when memory is the absolute constraint and you've already proven the reversal trick won't cut it (e.g., in embedded systems where you can't afford the recursion stack). In practice, the reversal algorithm is almost always the better pick — same complexity, far easier to verify.

// io.thecodeforge — dsa tutorial

// Rotates array left by d using juggling algorithm
public class RotateByJuggling {
    public static void rotateLeft(int[] arr, int d) {
        int n = arr.length;
        if (n == 0 || d % n == 0) return;
        d = d % n;
        int cycles = gcd(n, d);
        for (int start = 0; start < cycles; start++) {
            int temp = arr[start];
            int current = start;
            while (true) {
                int next = (current - d + n) % n;
                if (next == start) break;
                arr[current] = arr[next];
                current = next;
            }
            arr[current] = temp;
        }
    }

    private static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static void main(String[] args) {
        int[] data = {1, 2, 3, 4, 5, 6};
        rotateLeft(data, 2);
        System.out.println(java.util.Arrays.toString(data));
    }
}

Edge Cases That Will Fail Your Rotate If You're Not Looking

Most tutorials show you the happy path: n > d > 0. Real systems don't care about your happy path. Here are the three edge cases that'll bite you.

First, d >= n. If d is larger than the array length, rotating by d is identical to rotating by d % n. Ignore this and you'll throw an IndexOutOfBoundsException when you try to access arr[d] beyond the boundary. Always normalize: d = d % arr.length.

Second, n <= 1. An array of size 0 or 1 has nothing to rotate. Your reversal algorithm's reverse call on empty range is fine, but the juggling algorithm's gcd(0, d) will blow up with division by zero. Guard it with an early return.

Third, negative d. The problem spec usually says non-negative, but APIs don't. A negative d should rotate right. If your code doesn't handle that, your CI pipeline will catch it — or worse, a customer's nightly job will fail. Map negative d to (n - (-d % n)) % n.

Code defensively. These three guards take five lines and save hours of debugging.

// io.thecodeforge — dsa tutorial

public class RotateWithEdgeGuards {
    public static void rotateLeft(int[] arr, int d) {
        int n = arr.length;
        if (n <= 1) return;                         // Edge: trivial
        d = d % n;                                  // Edge: d >= n
        if (d < 0) d = (n - (-d % n)) % n;          // Edge: negative d
        if (d == 0) return;
        reverse(arr, 0, d - 1);
        reverse(arr, d, n - 1);
        reverse(arr, 0, n - 1);
    }

    private static void reverse(int[] arr, int left, int right) {
        while (left < right) {
            int tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            left++; right--;
        }
    }

    public static void main(String[] args) {
        int[] data = {1, 2, 3, 4, 5};
        rotateLeft(data, 7);  // d larger than n
        System.out.println(java.util.Arrays.toString(data));
    }
}