Array Rotation: Left and Right Rotation Algorithms

Key Insights

The reversal algorithm is the most practical choice for production code—it achieves O(n) time with O(1) space while remaining easy to understand and implement correctly.
Array rotation appears in disguise across many problems: circular buffers, string rotation checks, scheduling systems, and even some sorting algorithms rely on rotation as a primitive operation.
Before implementing manual rotation, check your language’s standard library—Python’s collections.deque and slice operations, JavaScript’s splice, and similar built-ins often handle edge cases you might miss.

Introduction to Array Rotation

Array rotation shifts all elements in an array by a specified number of positions, with elements that fall off one end wrapping around to the other. Left rotation moves elements toward the beginning (index 0), while right rotation moves them toward the end.

Consider an array [1, 2, 3, 4, 5]. A left rotation by 2 positions yields [3, 4, 5, 1, 2]—elements shift left, and the first two elements wrap to the end. A right rotation by 2 produces [4, 5, 1, 2, 3]—elements shift right, and the last two wrap to the beginning.

This operation isn’t just an academic exercise. Circular buffers in embedded systems use rotation logic for efficient FIFO queues. Round-robin schedulers rotate task lists to ensure fair CPU allocation. Image processing algorithms rotate pixel matrices. Even the classic “check if string A is a rotation of string B” problem reduces to array rotation.

Understanding rotation algorithms matters because the naive approach is deceptively expensive, and the optimal solutions reveal elegant patterns you’ll recognize in other contexts.

Naive Approach: One-by-One Rotation

The most intuitive approach rotates the array one position at a time, repeating k times. For left rotation, store the first element, shift everything left by one, then place the stored element at the end.

def rotate_left_naive(arr, k):
    n = len(arr)
    k = k % n  # Handle k > n
    
    for _ in range(k):
        # Store first element
        temp = arr[0]
        # Shift all elements left by one
        for i in range(n - 1):
            arr[i] = arr[i + 1]
        # Place stored element at end
        arr[n - 1] = temp
    
    return arr

# Example: [1, 2, 3, 4, 5] rotated left by 2 → [3, 4, 5, 1, 2]

function rotateLeftNaive(arr, k) {
    const n = arr.length;
    k = k % n;
    
    for (let rotation = 0; rotation < k; rotation++) {
        const temp = arr[0];
        for (let i = 0; i < n - 1; i++) {
            arr[i] = arr[i + 1];
        }
        arr[n - 1] = temp;
    }
    
    return arr;
}

This runs in O(n × k) time. When k approaches n, you’re doing nearly n² operations. For an array of 10,000 elements rotated by 9,999 positions, that’s approximately 100 million operations. We can do much better.

Using Temporary Array

The temporary array approach trades space for time. Copy the elements that will wrap around, shift the remaining elements, then copy the stored elements back.

def rotate_left_temp_array(arr, k):
    n = len(arr)
    k = k % n
    
    if k == 0:
        return arr
    
    # Step 1: Store first k elements (these will wrap to end)
    temp = arr[:k]  # [1, 2] for k=2
    
    # Step 2: Shift remaining elements to the front
    # [3, 4, 5] moves to positions [0, 1, 2]
    for i in range(n - k):
        arr[i] = arr[i + k]
    
    # Step 3: Place stored elements at the end
    # [1, 2] goes to positions [3, 4]
    for i in range(k):
        arr[n - k + i] = temp[i]
    
    return arr

# Visual walkthrough for [1, 2, 3, 4, 5], k=2:
# temp = [1, 2]
# After shift: [3, 4, 5, 4, 5]  (last two will be overwritten)
# After copy:  [3, 4, 5, 1, 2]  ✓

This achieves O(n) time but requires O(k) auxiliary space—or O(n) in the worst case when k ≈ n. For most applications, this trade-off is acceptable. Memory is cheap, and the code is readable.

However, in memory-constrained environments or when processing massive arrays, we need O(1) space solutions.

Juggling Algorithm (GCD-Based)

The juggling algorithm divides elements into sets based on the GCD of array length and rotation count. Each set is rotated independently, with elements jumping k positions at a time within their cycle.

The insight: if you start at index i and keep jumping k positions (wrapping around), you’ll eventually return to index i. The number of such independent cycles equals GCD(n, k).

import math

def rotate_left_juggling(arr, k):
    n = len(arr)
    k = k % n
    
    if k == 0:
        return arr
    
    # Number of cycles = GCD(n, k)
    num_cycles = math.gcd(n, k)
    
    for cycle_start in range(num_cycles):
        temp = arr[cycle_start]
        current = cycle_start
        
        while True:
            # Calculate next position in this cycle
            next_pos = (current + k) % n
            
            if next_pos == cycle_start:
                break
            
            arr[current] = arr[next_pos]
            current = next_pos
        
        arr[current] = temp
    
    return arr

# Example: [1, 2, 3, 4, 5, 6], k=2
# GCD(6, 2) = 2, so 2 cycles
# Cycle 1: indices 0 → 2 → 4 → 0 (elements 1, 3, 5)
# Cycle 2: indices 1 → 3 → 5 → 1 (elements 2, 4, 6)
# Result: [3, 4, 5, 6, 1, 2]

The juggling algorithm achieves O(n) time with O(1) space. Each element moves exactly once. However, the logic is harder to follow, and off-by-one errors are easy to introduce. I rarely recommend it for production code unless you’re in a severely memory-constrained environment.

Reversal Algorithm

The reversal algorithm is my preferred approach. It’s elegant, efficient, and easy to verify correctness. The key insight: a left rotation by k is equivalent to three reversals.

For left rotation by k:

Reverse the first k elements
Reverse the remaining n-k elements
Reverse the entire array

def reverse(arr, start, end):
    """Reverse arr[start:end+1] in place."""
    while start < end:
        arr[start], arr[end] = arr[end], arr[start]
        start += 1
        end -= 1

def rotate_left_reversal(arr, k):
    n = len(arr)
    k = k % n
    
    if k == 0:
        return arr
    
    # [1, 2, 3, 4, 5], k=2
    reverse(arr, 0, k - 1)      # [2, 1, 3, 4, 5]
    reverse(arr, k, n - 1)      # [2, 1, 5, 4, 3]
    reverse(arr, 0, n - 1)      # [3, 4, 5, 1, 2] ✓
    
    return arr

def rotate_right_reversal(arr, k):
    n = len(arr)
    k = k % n
    
    if k == 0:
        return arr
    
    # [1, 2, 3, 4, 5], k=2
    # Right rotation by k = Left rotation by (n-k)
    # Or use this direct approach:
    reverse(arr, 0, n - 1)      # [5, 4, 3, 2, 1]
    reverse(arr, 0, k - 1)      # [4, 5, 3, 2, 1]
    reverse(arr, k, n - 1)      # [4, 5, 1, 2, 3] ✓
    
    return arr

function reverse(arr, start, end) {
    while (start < end) {
        [arr[start], arr[end]] = [arr[end], arr[start]];
        start++;
        end--;
    }
}

function rotateRightReversal(arr, k) {
    const n = arr.length;
    k = k % n;
    
    if (k === 0) return arr;
    
    reverse(arr, 0, n - 1);
    reverse(arr, 0, k - 1);
    reverse(arr, k, n - 1);
    
    return arr;
}

Why does this work? Think of the array as two blocks: A (first k elements) and B (remaining elements). We want to transform AB into BA. Reversing A gives us A’B. Reversing B gives us A’B’. Reversing the whole thing gives us (A’B’)’ = BA.

Block Swap Algorithm

The block swap algorithm recursively swaps blocks of elements. If rotating left by k, we want to swap the first k elements with the last k elements, then handle the remaining middle portion.

def rotate_left_block_swap(arr, k):
    n = len(arr)
    k = k % n
    
    if k == 0 or k == n:
        return arr
    
    left = 0
    right = n - k
    
    while left != right:
        if left < right:
            # Left block is smaller, swap it with rightmost portion
            for i in range(k):
                arr[left + i], arr[right + i] = arr[right + i], arr[left + i]
            left += k
        else:
            # Right block is smaller
            block_size = n - right
            for i in range(block_size):
                arr[left + i], arr[right + i] = arr[right + i], arr[left + i]
            right += block_size
    
    return arr

Block swap also achieves O(n) time and O(1) space. It’s conceptually interesting but harder to implement correctly than the reversal algorithm. In practice, I’ve seen more bugs in block swap implementations than reversal implementations.

Comparison and When to Use Each

Algorithm	Time	Space	Readability	Best Use Case
Naive	O(n×k)	O(1)	High	Tiny arrays, k=1
Temp Array	O(n)	O(k)	High	General purpose, memory available
Juggling	O(n)	O(1)	Low	Memory-critical systems
Reversal	O(n)	O(1)	Medium-High	Production code, interviews
Block Swap	O(n)	O(1)	Medium	Academic interest

For production code, use your language’s built-in operations first:

from collections import deque

# Python: deque.rotate() - negative for left, positive for right
d = deque([1, 2, 3, 4, 5])
d.rotate(-2)  # Left rotation by 2
print(list(d))  # [3, 4, 5, 1, 2]

# Python: Slicing (creates new list)
arr = [1, 2, 3, 4, 5]
k = 2
rotated = arr[k:] + arr[:k]  # Left rotation
print(rotated)  # [3, 4, 5, 1, 2]

// JavaScript: splice + concat
function rotateLeft(arr, k) {
    k = k % arr.length;
    return arr.slice(k).concat(arr.slice(0, k));
}

// In-place using splice
function rotateLeftInPlace(arr, k) {
    k = k % arr.length;
    arr.push(...arr.splice(0, k));
    return arr;
}

These built-ins handle edge cases, are well-tested, and communicate intent clearly. Only implement manual rotation when you need in-place modification with strict memory constraints, or when you’re in an interview setting where that’s the point.

The reversal algorithm remains my recommendation for manual implementation. It’s the right balance of efficiency, correctness, and maintainability. When someone asks why it works, you can explain it in one sentence: “Reverse the parts, then reverse the whole.”