DSA Intermediate

Rotate Array Problem Explained — 3 Approaches, Real Trade-offs

📅 March 05, 2026 ⏱ 5 min read 🎯 Intermediate

Where developers are forged. · Structured learning · Free forever.

📍 Part of: Arrays & Strings → Topic 10 of 13

Rotate array problem solved 3 ways in Java — brute force, extra array, reversal trick, and cyclic replacement.

⚙️ Intermediate — basic DSA knowledge assumed

In this tutorial, you'll learn

Rotate array problem solved 3 ways in Java — brute force, extra array, reversal trick, and cyclic replacement.

Always reduce k with k % n before rotating — skipping this turns an O(n) algorithm into O(n²) or causes silent redundant full cycles.
The reversal trick works because two inversions cancel out: reversing the whole array then reversing each segment independently restores internal order in a new overall position.
The destination-index formula (i + k) % n loop when gcd(n, k) > 1 and the cycle does not return to the starting index — Fix: use a count variable to track total elements moved, and terminate is reusable across circular buffers, Caesar ciphers, and round-robin schedulers — memorise it, not just for rotations.

✦ Plain-English analogy ✦ Real code with output ✦ Interview questions

⚡Quick Answer

Brute force: O(n*k) time, O(1) space. Rotate one step at a time. Only for tiny k.
Extra array: O(n) time, O(n) space. Clean and readable. Use when memory is free.
Reversal trick: O(n) time, O(1) space. Three in-place reversals. Optimal.
Cyclic replacement: O(n) time, O(1) space. Move elements directly to final positions in cycles.
Circular buffers, round-robin schedulers, and job queues all use array rotation.
Always normalize k = k % n first. Without it, large k causes redundant full cycles.
Off-by-one in reversal boundaries. reverse(0, steps) instead of reverse(0, steps-1) corrupts the result.

🚨 START HERE

Array Rotation Triage

Rapid checks to isolate array rotation bugs.

🟡Rotation produces wrong result when k >= array length.

Immediate ActionCheck if k = k % n is the first line of the function.

Commands

Print k before and after normalization: System.out.println("k=" + k + " n=" + n + " k%n=" + (k % n))

Test with k = n: should return original array unchanged

Fix NowAdd k = k % n as the first line. Add if (k == 0) return; for no-op case.

🟡Reversal trick produces result with two adjacent elements in wrong order.

Immediate ActionCheck reversal boundary arguments: reverse(0, k-1) and reverse(k, n-1).

Commands

Print the intermediate state after each reversal step

Verify: after step 1 (full reverse), the array is fully reversed

Fix NowChange reverse(0, steps) to reverse(0, steps - 1). The first segment is [0, k-1].

🟡ArrayIndexOutOfBoundsException on rotation.

Immediate ActionCheck if k is used as a boundary without normalization.

Commands

Print: System.out.println("k=" + k + " n=" + n + " k-1=" + (k-1))

If k-1 >= n, the normalization is missing

Fix NowAdd k = k % n before any reversal calls.

🟡Extra array approach returns original array unchanged.

Immediate ActionCheck if System.arraycopy is called after populating the buffer.

Commands

Print buffer after population: System.out.println(Arrays.toString(buffer))

If buffer is correct but original is unchanged, the copy-back is missing

Fix NowAdd System.arraycopy(buffer, 0, elements, 0, length) after the destination loop.

Production IncidentRound-Robin Load Balancer Stuck on Same Server: Missing Modulo on Rotation StepA load balancer used array rotation to cycle through a pool of 8 backend servers. The rotation step was incremented by 1 per request but never reduced modulo the pool size. After 8 requests, the rotation step was 8 — equal to the pool size. The reversal trick reversed the entire array (step 1), then reversed the first 8 elements (step 2 — the entire array again), then reversed 0 elements (step 3). The result was the original array, but the rotation step continued to grow. At step 16, the reversal boundaries became negative (steps - 1 = 7, which happened to be valid), producing a rotated array that sent all traffic to 2 servers instead of distributing across 8.

SymptomAfter 16 requests, the load balancer sent 75% of traffic to 2 servers and 25% to the remaining 6. Server health checks showed 2 servers at 95% CPU and 6 servers at 5% CPU. P99 latency spiked from 12ms to 800ms on the overloaded servers. No configuration changes, no traffic increase.

AssumptionA health check configuration change caused the load balancer to prefer healthy servers. The team spent 3 hours checking health check intervals, server weights, and connection pool settings.

Root causeThe rotation step was incremented by 1 per request but never reduced modulo the pool size (8). After 8 requests, step = 8. The reversal trick with k=8 on an 8-element array: reverse all (back to original), reverse first 8 (back to reversed), reverse last 0 (no-op). Result: reversed array — traffic distribution inverted. At step 9, k=9: reverse all, reverse first 9 (out of bounds — ArrayIndexOutOfBoundsException caught by try-catch, returning original array). The broad try-catch masked the error. At step 16, k=16: 16 % 8 = 0, but the code did not normalize, so k=16 was used directly, producing unexpected results.

Fix1. Added k = k % poolSize as the first line of the rotation function. Now step 8 produces k=0 (no rotation), step 9 produces k=1 (correct rotation). 2. Removed the broad try-catch. Let ArrayIndexOutOfBoundsException propagate so boundary errors surface immediately. 3. Added a unit test: rotate 8-element array by 8 must return the original array. rotate by 9 must equal rotate by 1. 4. Added a metric: rotation_step_normalized_total to track how often normalization changes the step value. 5. Added a validation: after rotation, verify the array has the same elements (just reordered). Use a checksum comparison.

Key Lesson

Always normalize k = k % n before rotating. Without it, k >= n causes redundant work or incorrect results.Broad try-catch blocks mask real errors. The ArrayIndexOutOfBoundsException would have caught the bug immediately.Test with k = n (full cycle), k = n+1 (one past full cycle), and k = 2n (two full cycles). All should produce correct results.Round-robin rotation must normalize the step. The step counter grows unbounded but the rotation is periodic with period n.Add a post-rotation validation: verify the array contains the same elements in rotated order.

Production Debug GuideSymptom-first investigation path for rotation bugs.

Rotation produces wrong result when k >= n.→Check if k is normalized with k = k % n before the rotation logic. Without normalization, k = n reverses the array twice (back to original), and k > n produces unpredictable results.

Reversal trick produces result with two adjacent elements swapped.→Check the reversal boundaries. reverse(0, steps) should be reverse(0, steps - 1). The second segment starts at steps, not steps + 1.

Rotation is O(n*k) instead of O(n) despite using the reversal trick.→Check if the brute force approach is being used accidentally — rotating one step at a time k times. If k is large (close to n), the reversal trick is O(n) while brute force is O(n^2).

ArrayIndexOutOfBoundsException on rotation with k >= n.→Check if k is normalized before being used as a boundary index. reverse(0, k - 1) with k = n causes reverse(0, n - 1) which is valid, but reverse(0, k) with k = n causes reverse(0, n) which is out of bounds.

Left rotation produces the same result as right rotation.→Check if the reversal order is correct. Right rotation: reverse all, reverse first k, reverse last n-k. Left rotation: reverse first k, reverse last n-k, reverse all. The order matters.

Extra array approach returns unmodified array.→Check if the buffer is copied back to the original array. The rotation places elements in the buffer, but the original array is unchanged until System.arraycopy is called.

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.

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.

io/thecodeforge/algo/ArrayRotationOverview.java · JAVA

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748

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]
    }
}

▶ Output

Before: [1, 2, 3, 4, 5, 6, 7]
After k=3: [5, 6, 7, 1, 2, 3, 4]
k=7 (effective k=2): [4, 5, 1, 2, 3]
k=3 (full cycle): [1, 2, 3]

Mental Model

Why Three Reversals Work

Think of it as: mirror everything, then un-mirror the two halves. The global mirror moves elements to the right position. The local un-mirrors fix the internal order.

Step 1 (reverse all): puts tail at front, head at back — both reversed internally.
Step 2 (reverse first k): fixes the internal order of the new front section.
Step 3 (reverse last n-k): fixes the internal order of the new back section.
Each element is touched at most twice. O(n) total swaps.
No extra memory — all reversals are in-place with a single temp variable.

📊 Production Insight

A circular buffer implementation used the reversal trick to physically rotate the buffer when the read pointer wrapped around. The buffer held 10,000 sensor readings. Rotating by the read offset: O(n) time, O(1) space. The alternative (allocating a new buffer and copying) would have caused GC pressure at 1,000 rotations per second. The reversal trick eliminated all buffer allocations.

🎯 Key Takeaway

The reversal trick achieves O(n) time, O(1) space with three in-place reversals. The global mirror moves elements to the correct position. The local un-mirrors fix internal order. Always normalize k = k % n first.

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.

io/thecodeforge/algo/BruteForceRotation.java · JAVA

123456789101112131415161718192021222324252627282930

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.

📊 Production Insight

A job scheduler rotated a task queue by 1 slot per tick using brute force. With 500 tasks and 1,000 ticks per second, the inner loop performed 500,000 element shifts per second. CPU utilization was 15% just for queue rotation. Switching to the reversal trick with k=1: 1,000 reversals per second, each touching 500 elements twice = 1,000,000 swaps vs 500,000 shifts. The reversal trick was actually slower for k=1 because each reversal touches elements twice. The real fix: use a circular buffer with a pointer offset — O(1) per rotation, no element movement at all.

🎯 Key Takeaway

Brute force is O(n*k) time, O(1) space. Only use it for tiny k and small n. Always normalize k = k % n first. For k=1, a circular buffer pointer offset is O(1) — no element movement needed.

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.

io/thecodeforge/algo/ExtraArrayRotation.java · JAVA

12345678910111213141516171819202122232425262728293031323334353637

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)
    }
}

▶ Output

Before: [101, 102, 103, 104, 105]
After k=2: [104, 105, 101, 102, 103]

💡Pro Tip: The Formula is Reusable

Right rotation destination: (i + k) % n. Element at index i moves forward by k.
Left rotation destination: (i - k by k.
The +n in left rotation prevents negative indices. Java: -1 % 5 = -1 (not 4).
This formula is the basis of circular buffer access without physical rotation.
Memorize it — it appears in round-robin schedulers, Caesar ciphers, and ring buffers.

📊 Production Insight

A music playlist service used the extra array approach to implement 'shuffle-rotate' — rotating the playlist by a random k to create a shuffled feel. The playlist had 10,000 tracks. Allocating a 10,000-element int[] buffer: 40KB. This was negligible compared to the 2GB heap. The code was simple, correct, and easy to review. The team chose clarity over O(1) space because the memory cost was irrelevant and the code was reviewed by junior engineers who needed to understand it.

🎯 Key Takeaway

Extra array approach is O(n) time, O(n) space. The destination formula (i + k) % n is reusable across circular buffers, Caesar ciphers, and round-robin schedulers. Use this approach when memory is free and clarity matters.

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.

io/thecodeforge/algo/ReversalTrickRotation.java · JAVA

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748

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));
    }
}

▶ Output

Original: [1, 2, 3, 4, 5, 6, 7]
After k=3: [5, 6, 7, 1, 2, 3, 4]
After k=1: [105, 101, 102, 103, 104]
k=12 (effective k=2): [32, 16, 255, 128, 64]

🔥Interview Gold: Prove It with a Tiny Example

Trace [1,2,3,4,5] k=2: [5,4,3,2,1] → [4,5,3,2,1] → [4,5,1,2,3].
Trace [1,2,3,4,5,6,7] k=3: [7,6,5,4,3,2,1] → [5,6,7,4,3,2,1] → [5,6,7,1,2,3,4].
Each step is a simple two-pointer swap. No complex index arithmetic.
The global mirror + local un-mirrors is the key insight.
If asked 'why not just reverse the two halves without the global reverse?' — the halves are not adjacent after rotation. The global reverse brings them into position.

📊 Production Insight

A high-frequency trading system rotated a circular order book by k slots to align the best bid/ask with index 0. The order book had 1,000 entries. The reversal trick rotated in O(n) time, O(1) space — no heap allocation during market hours when GC pauses cost money. The alternative (extra array) would have allocated 8KB per rotation, causing GC pressure at 10,000 rotations per second. The reversal trick eliminated all allocations and kept GC pause time at 0ms.

🎯 Key Takeaway

The reversal trick is the optimal solution: O(n) time, O(1) space. Trace a small example to prove correctness. The global mirror + local un-mirrors is the key insight. This is the answer LeetCode 189 expects.

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.

io/thecodeforge/algo/CyclicReplacementRotation.java · JAVA

12345678910111213141516171819202122232425262728293031323334353637383940414243444546

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));
    }
}

▶ Output

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

🔥When to Use Cyclic Replacement vs Reversal Trick

Reversal trick: simpler code, easier to debug. Preferred in interviews.
Cyclic replacement: each element moved exactly once. More elegant mathematically.
Number of cycles = gcd(n, k). Each cycle processes n/gcd(n,k) elements.
Cyclic replacement is harder to implement correctly (cycle completion tracking).
Both achieve O(n) time, O(1) space. Choose based on code simplicity.

📊 Production Insight

A ring buffer implementation used cyclic replacement to physically rotate the buffer when the read pointer offset exceeded a threshold. The advantage over the reversal trick: each element was moved exactly once (vs twice in the reversal trick). For a 100,000-element buffer rotated 100 times per second, cyclic replacement performed 10 million element moves per second vs 20 million for the reversal trick. The 2x reduction in memory writes reduced cache invalidation overhead by 30%.

🎯 Key Takeaway

Cyclic replacement moves each element exactly once to its final position. Number of cycles = gcd(n, k). It is mathematically elegant but harder to implement than the reversal trick. In interviews, prefer the reversal trick for simplicity.

🗂 Array Rotation Approaches Compared

Choosing the right approach based on constraints and scale.

Aspect	Brute Force (One-by-One)	Extra Array (Buffer)	Reversal Trick (In-Place)	Cyclic Replacement
Time Complexity	O(n * k)	O(n)	O(n)	O(n)
Space Complexity	O(1)	O(n)	O(1)	O(1)
Code Readability	Very easy to follow	Easy to follow	Requires explanation	Hard to get right
Handles k > n?	Only with modulo guard	Only with modulo guard	Only with modulo guard	Only with modulo guard
Best Use Case	Tiny arrays, tiny k	When memory isn't a constraint	Production / interview code	Low-level optimization
Mutation of input?	Yes (in-place)	Yes (copies buffer back)	Yes (in-place)	Yes (in-place)
Risk of TLE on large n?	High when k is large	None	None	None
LeetCode 189 optimal?	No — TLE on large inputs	Partially (fails O(1) space)	Yes — accepted optimal	Yes — accepted optimal
Elements touched	n per step, n*k total	n (write to buffer) + n (copy back)	At most 2n (each reversal touches elements)	Exactly n (each element moved once)

🎯 Key Takeaways

Always reduce k with k % n before rotating — skipping this turns an O(n) algorithm into O(n²) or causes silent redundant full cycles.
The reversal trick works because two inversions cancel out: reversing the whole array then reversing each segment independently restores internal order in a new overall position.
The destination-index formula (i + k) % n loop when gcd(n, k) > 1 and the cycle does not return to the starting index — Fix: use a count variable to track total elements moved, and terminate is reusable across circular buffers, Caesar ciphers, and round-robin schedulers — memorise it, not just for rotations.
Choose your approach based on constraints: brute force for throwaway scripts with tiny data, extra array when memory is free and clarity matters, reversal trick for production systems and any interview that mentions O(1) space.
Cyclic replacement moves each element exactly once vs twice in the reversal trick. It is mathematically elegant but harder to implement correctly.
For left rotation: reverse first k, reverse last n-k, then reverse all. The order of reversals matters — it is different from right rotation.
Test with k = n (full cycle), k = n+1 (one past full cycle), k = 0 (no rotation), and k > n (multiple full cycles). All must produce correct results.
In production, consider circular buffer pointer offsets for O(1) rotation without any element movement. Physical rotation is only needed when the rotated order must be persisted.

⚠ Common Mistakes to Avoid

✕Not reducing k with modulo before rotating — If k equals n, you do a full cycle of n×n operations for free and return the original array. If k > n you silently do extra useless work. The

Symptom

is mysteriously slow performance on large inputs that pass correctness tests.

Fix

always write steps = steps % length as the first real line of your function, before any loop or reversal.

✕Off-by-one in the reversal boundaries — A common error is writing reverse(elements, 0, steps) instead of reverse(elements, 0, steps - 1). Since Java arrays are zero-indexed and both endpoints are inclusive in the typical two-pointer reverse, including index 'steps' bleeds into the second segment and corrupts the result. The

Symptom

is a result that looks almost right but has two adjacent elements in the wrong order.

Fix

double-check your boundary arguments — the first segment is [0, steps-1], the second is [steps, length-1].

✕Confusing left rotation and right rotation — Right rotation by k moves elements toward higher indices, wrapping the tail to the front. Left rotation by k does the opposite. The mistake usually comes from misreading the problem statement and then being confused when the output looks like a mirror of what's expected. Fix: test with [1,2,3,4,5] and k=1. Right rotation should give [5,1,2,3,4]. Left rotation should give [2,3,4,5,1]. Lock this into muscle memory and always verify with a single-step test case before running your full solution.

Fix

test with [1,2,3,4,5] and k=1. Right rotation should give [5,1,2,3,4]. Left rotation should give [2,3,4,5,1]. Lock this into muscle memory and always verify with a single-step test case before running your full solution.

✕Forgetting to copy the buffer back in the extra array approach

Symptom

the method returns the original array unchanged. The rotation places elements in the buffer, but the original array is unmodified until System.arraycopy is called —

Fix

always call System.arraycopy(buffer, 0, elements, 0, length) after the destination loop.

✕Using the reversal trick for left rotation without adjusting the order

Symptom

left rotation produces the same result as right rotation —

Fix

for left rotation by k, reverse first k, reverse last n-k, then reverse all. The order of the three reversals matters.

✕Not handling the k == 0 edge case after normalization

Symptom

the algorithm performs unnecessary reversals when k % n == 0 —

Fix

add if (k == 0) return; after normalization to short-circuit the no-op case.

✕Using the extra array approach without pre-sizing

Symptom

ArrayList resizing causes O(n log n) total work instead of O(n) —

Fix

use new int[length] for the buffer, not ArrayList.add().

✕Cyclic replacement with incorrect cycle termination

Symptom

infinite the outer loop when count == n.

Interview Questions on This Topic

QCan you rotate an array in-place using O(1) extra space? Walk me through your approach and prove it's correct with a small example.
QWhat happens when k is greater than or equal to the array length? How does your solution handle that edge case, and why is the modulo operation the right fix?
QIf I asked you to rotate left instead of right, how would you adapt your reversal-trick solution? What changes in the boundary indices, and can you derive the formula for the left-rotation destination index?
QCompare the reversal trick with cyclic replacement. Both achieve O(n) time, O(1) space. When would you choose one over the other?
QHow would you implement a circular buffer that supports O(1) rotation without physically moving elements? What is the relationship between the rotation step and the read pointer offset?
QYour round-robin load balancer rotates a server pool by 1 slot per request. After 16 requests, traffic is unevenly distributed. What is the most likely root cause?
QHow would you rotate a 2D matrix 90 degrees clockwise? How does this relate to array rotation?
QExplain the gcd(n, k) relationship in cyclic replacement. Why does the number of cycles equal gcd(n, k)?
QHow would you rotate an array in-place without using any extra variable (not even a temp for swapping)? Is this possible?
QDescribe a production scenario where array rotation choice impacted performance. What approach did you use and what was the GC/cache impact?

Frequently Asked Questions

What is the most efficient way to rotate an array in Java?

The reversal trick achieves O(n) time and space — the theoretical k elements wrap to the back. For a right rotation the destination formula is (i + k) % n; for left rotation it's (i - k + n) % n. The +n in the left-rotation formula prevents negative indices.

Why does rotating an array by k give the same result as rotating by k % n?

After exactly n rotations (where n is the array length), every element has returned to its original position — you've done a full cycle. Any additional rotations beyond a full cycle just repeat positions you've already visited. So rotating by 7 on a 5-element array is identical to rotating by 7 % 5 = 2. Applying the modulo before your algorithm is a correctness and performance guard in one.

Why do we normalize k = k % n?

Rotating by n is a no-op. Rotating by n+2 is the same as rotating by 2. Normalizing with % n eliminates full rotations, ensuring we do the minimum work. Without it, we might reverse far more elements than necessary for large k values.

How does a cyclic replacement approach compare to the reverse trick?

Cyclic replacement also achieves O(n) time and O(1) space. It moves each element directly to its final position in cycles. The reverse trick is generally simpler to implement and reason about, so it is preferred in interviews.

Can you rotate an array without any element movement?

Yes — use a circular buffer with a pointer offset. Instead of moving elements, maintain a read pointer that starts at offset k. Access element i at position (i + k) % n. This is O(1) per access and O(1) per rotation (just increment the offset). The physical array is never modified. This is how production circular buffers work.

What is the relationship between gcd(n, k) and cyclic replacement?

The number of cycles in cyclic replacement equals gcd(n, k). Each cycle processes n / gcd(n, k) elements. Total elements processed: gcd(n, k) * (n / gcd(n, k)) = n. When gcd(n, k) = 1 (n and k are coprime), there is exactly one cycle. When gcd(n, k) = n (k is a multiple of n), each element is its own cycle (no movement needed after normalization).

🔥

Naren Founder & Author

Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.

About Naren Get in touch

Forged with 🔥 at TheCodeForge.io — Where Developers Are Forged