Rotate Array by d

Rotate Array by d asks you to shift every element of an array by d positions. The naive moves are easy but wasteful; the elegant answer is a trick worth memorizing — three in-place reversals that rearrange the whole array with no extra memory.

The slow way first

The obvious idea: rotate one position at a time. Save the first element, shift everything left by one, drop the saved element at the end — then repeat d times. Each pass is O(n) and we do d passes, so it is O(n·d) time. For a large array and a large d that is far too slow.

A second naive idea uses a temporary array: copy each element to its rotated index. That is O(n) time but costs O(n) extra space. Can we get O(n) time and O(1) space? Yes — by reversing.

The idea: three reversals flip it into place

Here is the trick. To rotate left by d:

1. Reverse the first d elements — the slice [0 .. d-1].
2. Reverse the remaining n - d elements — the slice [d .. n-1].
3. Reverse the whole array — the slice [0 .. n-1].

That is it. Three reversals, each a simple two-pointer swap loop, and the array lands rotated.

Why does it work? Reversing the two halves separately puts the elements of each half in backward order. The final full reverse flips everything back to forward order and swaps the two blocks — which is exactly a rotation.

Walk through it

Step through the animation on [1,2,3,4,5,6,7] with d = 2. In each phase the l and r pointers mark the slice being reversed; they start at the two ends and swap inward until they meet. Phase 1 flips 1,2 to 2,1. Phase 2 flips the back five to 7,6,5,4,3. Phase 3 reverses the entire array, and the cells settle into [3,4,5,6,7,1,2].

Pseudocode

reverse(l, r):                      # flip a slice in place, two pointers
    while l < r:
        swap arr[l] and arr[r]
        l = l + 1
        r = r - 1
 
rotate(arr, d):
    n = length of arr
    d = d mod n                      # rotating by n is a no-op
    reverse(0, d - 1)                # flip the first d
    reverse(d, n - 1)                # flip the rest
    reverse(0, n - 1)                # flip the whole array
    return arr

The Python solution

def rotate(arr, d):
    def reverse(l, r):
        while l < r:
            arr[l], arr[r] = arr[r], arr[l]
            l += 1
            r -= 1
    n = len(arr)
    d %= n
    reverse(0, d - 1)
    reverse(d, n - 1)
    reverse(0, n - 1)
    return arr

• reverse(l, r) is a tiny helper: while the two pointers have not crossed, swap the ends and step them inward. This is the classic two-pointer reversal.
• d %= n guards against a d larger than the array (rotating by n lands back where you started, so only d mod n matters).
• The three reverse calls are the whole algorithm: first d, then the rest, then everything.
• Every swap is in place, so we never allocate a second array — that is the O(1) space win.

Complexity

Each of the three reversals touches each element at most once, so the total work is linear — O(n) time. No extra array means O(1) space. That combination is what makes the reversal trick the textbook answer.

When this pattern shows up

Practice