Array Rotation in O(n): Juggling, Reversal and Block Swap

To rotate an array of n elements by k positions, the fastest practical approach is the reversal algorithm: O(n) time, O(1) extra space, three loops. Juggling and block swap reach the same bounds. To go the other way and find the rotation offset between an array and its rotated copy, use binary search if the array was sorted and has distinct values (O(log n)), and otherwise a linear scan or string matching on the doubled array (O(n)). Nothing can beat O(n) for an unsorted array, as explained below.

What rotation means

Rotating [1, 2, 3, 4, 5] left by 2 gives [3, 4, 5, 1, 2]. Rotating it right by 2 gives [4, 5, 1, 2, 3]. Rotating right by k is the same as rotating left by n - k, so you only ever need one direction.

Always reduce first: k = k % n. Rotating by n returns the original array, and in Python k % n also turns a negative k into the equivalent rotation in the other direction. Handle n == 0 before taking the modulo, or you get a division by zero.

Method	Time	Extra space	Writes
Copy into a new array	O(n)	O(n)	n
Reversal	O(n)	O(1)	about 2n element moves
Juggling (cycle leader)	O(n)	O(1)	exactly n
Block swap	O(n)	O(1)	at most n swaps
Rotating one step, k times	O(n * k)	O(1)	n * k

Method 1: copy into a new array

Element i moves to index (i + k) % n. In Python, slicing says the same thing in one line.

def rotate_copy(arr, k):
    n = len(arr)
    if n == 0:
        return []
    k %= n
    return arr[-k:] + arr[:-k] if k else arr[:]

print(rotate_copy([1, 2, 3, 4, 5, 6, 7], 3))  # [5, 6, 7, 1, 2, 3, 4]

The if k guard matters: arr[-0:] is the whole array, so without it k = 0 would return the array twice. This version is fine when the problem allows extra memory. Interviewers usually ask for the in-place versions next.

Method 2: reversal algorithm

To rotate right by k: reverse the whole array, then reverse the first k elements, then reverse the remaining n - k.

Trace for [1, 2, 3, 4, 5, 6, 7] with k = 3:

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

def rotate_right_reversal(arr, k):
    n = len(arr)
    if n == 0:
        return arr
    k %= n

    def reverse(i, j):
        while i < j:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
            j -= 1

    reverse(0, n - 1)
    reverse(0, k - 1)
    reverse(k, n - 1)
    return arr

print(rotate_right_reversal([1, 2, 3, 4, 5, 6, 7], 3))  # [5, 6, 7, 1, 2, 3, 4]

For a left rotation by d, reverse [0, d), then [d, n), then the whole array. This is the answer most interviewers expect for LeetCode 189 (Rotate Array): it is short, easy to get right, and has no number theory.

Method 3: juggling algorithm

Every element moves to (i + k) % n, so the indices split into gcd(n, k) independent cycles. Walk each cycle once, carrying one value forward. Each element is written exactly once, which makes this the method with the fewest writes.

from math import gcd

def rotate_right_juggling(arr, k):
    n = len(arr)
    if n == 0:
        return arr
    k %= n
    if k == 0:
        return arr
    for start in range(gcd(n, k)):
        i = start
        carry = arr[start]
        while True:
            j = (i + k) % n
            arr[j], carry = carry, arr[j]   # drop carry at j, pick up what was there
            i = j
            if i == start:
                break
    return arr

print(rotate_right_juggling([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], 3))
# [10, 11, 12, 1, 2, 3, 4, 5, 6, 7, 8, 9]

With n = 12 and k = 3 there are gcd(12, 3) = 3 cycles of 4 elements each: starting at 0 you visit 0, 3, 6, 9; starting at 1 you visit 1, 4, 7, 10; and so on. A common bug is to loop k times instead of gcd(n, k) times, or to forget that a single cycle does not cover the array when gcd > 1.

In practice the poor cache behavior of jumping around memory often makes reversal faster, even though juggling writes less.

Method 4: block swap

Treat the array as two blocks, A = the first d elements and B = the rest, so the array is AB and a left rotation by d must produce BA. Swap the shorter block with the matching part of the longer one, and recurse on what is left. It is the same idea as the Euclidean algorithm for gcd.

def rotate_left_block_swap(arr, d):
    n = len(arr)
    if n == 0:
        return arr
    d %= n
    if d == 0:
        return arr

    def swap(a, b, m):
        for t in range(m):
            arr[a + t], arr[b + t] = arr[b + t], arr[a + t]

    i, j = d, n - d          # sizes of the left and right blocks
    while i != j:
        if i < j:            # left block is shorter: swap it with the right block's tail
            swap(d - i, d - i + j, i)
            j -= i
        else:                # right block is shorter: swap it into place
            swap(d - i, d, j)
            i -= j
    swap(d - i, d, i)        # equal sizes: one last swap
    return arr

print(rotate_left_block_swap([1, 2, 3, 4, 5, 6, 7], 2))  # [3, 4, 5, 6, 7, 1, 2]

Block swap is the hardest of the four to write without a bug. Know that it exists, but write reversal in the interview unless you are asked for the minimum number of swaps.

Finding the rotation offset

This is the reverse problem: you are given an array and a rotated version of it (or a sorted array that was rotated), and you must find how far it was rotated. The right algorithm depends on what you know about the array.

Sorted array with distinct values: O(log n) binary search

If a sorted array was rotated, the rotation point is the index of the smallest element. Compare the middle element with the last one. If a[mid] > a[hi], the minimum is to the right of mid; otherwise it is at mid or to the left.

def rotation_point(a):
    """Index of the smallest element in a rotated sorted array of distinct values."""
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] > a[hi]:
            lo = mid + 1
        else:
            hi = mid
    return lo

print(rotation_point([4, 5, 6, 7, 0, 1, 2]))  # 4
print(rotation_point([1, 2, 3]))              # 0 (not rotated)

The sorted array was rotated right by rotation_point(a) positions (the smallest element started at index 0 and moved to that index), which is the same as rotating left by n - rotation_point(a). This is the core of LeetCode 153 (Find Minimum in Rotated Sorted Array) and the first step of 33 (Search in Rotated Sorted Array).

With duplicate values the comparison can be a tie, and then you cannot tell which side the minimum is on. The standard fix is to shrink hi by one on a tie (LeetCode 154). It still works, but the worst case, such as [2, 2, 2, 0, 1, 2] or an array of all equal values, degrades to O(n), and no algorithm can do better in that case because the single different element could be anywhere.

def rotation_point_with_duplicates(a):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] > a[hi]:
            lo = mid + 1
        elif a[mid] < a[hi]:
            hi = mid
        else:
            hi -= 1
    return lo

print(rotation_point_with_duplicates([2, 2, 2, 0, 1, 2]))  # 3

If the rotated array can have duplicates and you need the exact offset rather than any valid one, the answer may not be unique ([1, 1] is a rotation of itself by 0 or 1). Ask what the problem wants.

Unsorted array with distinct values: O(n), and that is optimal

If b is a rotation of a and all values are distinct, the offset is where b[0] sits in a. A scan finds it in O(n); a hash map built once makes every later lookup O(1), but building it costs O(n).

def find_shift_unique(a, b):
    """b == a rotated left by the returned amount (distinct values, b is a rotation of a)."""
    pos = {v: i for i, v in enumerate(a)}
    return pos.get(b[0], -1)

print(find_shift_unique([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))  # 2

Can you do better than linear? Not for arbitrary unsorted data. Where b[0] appears in a could be any of the n positions, and an algorithm that reads fewer than n entries of a can be fooled by an input that differs only in the unread entry. So a sublinear algorithm only exists when the array has structure, such as being sorted. If you must also verify that b really is a rotation, you have to compare all n elements anyway.

General arrays with duplicates: search in the doubled array

The classic trick: b is a rotation of a exactly when b appears as a contiguous subarray of a + a and both have the same length. The match position is the offset. Naive matching is O(n²) in the worst case; the KMP algorithm makes it O(n) time and O(n) space for the prefix table.

def prefix_function(p):
    pi = [0] * len(p)
    k = 0
    for i in range(1, len(p)):
        while k and p[i] != p[k]:
            k = pi[k - 1]
        if p[i] == p[k]:
            k += 1
        pi[i] = k
    return pi

def find_shift(a, b):
    """Return k such that b == a rotated left by k, or -1. Handles duplicates. O(n)."""
    n = len(a)
    if n != len(b):
        return -1
    if n == 0:
        return 0
    pi = prefix_function(b)
    k = 0
    for i, x in enumerate(a + a[:-1]):     # a + a without the last element is enough
        while k and x != b[k]:
            k = pi[k - 1]
        if x == b[k]:
            k += 1
        if k == n:
            return i - n + 1
    return -1

print(find_shift([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))  # 2
print(find_shift([1, 2, 3], [1, 3, 2]))              # -1
print(find_shift([1, 1, 2, 1], [1, 2, 1, 1]))        # 1

For strings, the one-liner len(a) == len(b) and b in a + a answers “is it a rotation?” and (a + a).find(b) returns the offset. For plain strings that is usually enough; for lists, or when the interviewer asks for a guaranteed O(n) bound, use KMP or the Z-algorithm as above.

Common mistakes

• Forgetting k %= n, which gives index errors or extra work when k > n.
• Mixing up left and right. Test with a small array where the answer is easy to see.
• Slicing with arr[-k:] when k = 0.
• Assigning arr = arr[-k:] + arr[:-k] inside a function that is meant to modify the input. That rebinds a local name; write arr[:] = ... to change the caller’s list (this uses O(n) extra space).
• Rotating one step at a time, k times. It is O(n * k) and is the first thing an interviewer expects you to improve on.
• Using the sorted-array binary search on an array that is not sorted before rotation.

Follow-up questions to expect

• Can you do it in place with O(1) extra space? (Reversal, juggling, block swap.)
• Why does juggling use gcd(n, k) cycles?
• How would you search for a target in a rotated sorted array in O(log n)? (Find the pivot, or compare against both ends of the half you are in.)
• What if the data is a linked list? Connect the tail to the head, walk n - k steps, and cut. See linked lists vs arrays for the trade-offs.
• What if the array is too large for memory? Rotation becomes an index mapping: keep the array as is and read element i at (i + offset) % n.

Python also has collections.deque, whose rotate(k) method rotates right by k in place. That is fine in real code, but in an interview you are normally expected to write the algorithm yourself.

Practice

Good problems to try next: Rotate Array (LeetCode 189), Find Minimum in Rotated Sorted Array (153), Search in Rotated Sorted Array (33), Rotate List (61), Rotate String (796) and Rotate Image (48). Binary search is covered in linear vs binary search. If you want to build up from list basics with step-by-step exercises, start with the Lists lesson or browse app.algocademy.com.