# Array Rotation

# Array Rotation

Array rotation shifts all elements by a fixed offset. Elements that move past one end reappear at the other end.

You use it when cyclic structure matters, such as scheduling, buffering, or rearranging data without changing relative order.

## Problem

Given an array $A$ of length $n$ and an integer $k$, rotate the array to the right by $k$ steps.

Each element moves from index $i$ to:

$$
(i + k) \bmod n
$$

## Structure

Original:

$$
A = [a_0, a_1, a_2, \dots, a_{n-1}]
$$

After rotation by $k$:

$$
A' = [a_{n-k}, a_{n-k+1}, \dots, a_{n-1}, a_0, a_1, \dots]
$$

## Algorithm

Use the reversal method for in-place rotation.

```id="array-rotation-reverse"
rotate_right(A, k):
    n = length(A)
    k = k mod n

    reverse(A, 0, n - 1)
    reverse(A, 0, k - 1)
    reverse(A, k, n - 1)
```

Helper:

```id="array-reverse"
reverse(A, l, r):
    while l < r:
        swap A[l], A[r]
        l += 1
        r -= 1
```

## Example

Let

$$
A = [8, 3, 5, 1, 9]
$$

and

$$
k = 2
$$

Steps:

| step            | array           |
| --------------- | --------------- |
| reverse all     | [9, 1, 5, 3, 8] |
| reverse first 2 | [1, 9, 5, 3, 8] |
| reverse rest    | [1, 9, 8, 3, 5] |

Result:

$$
[1, 9, 8, 3, 5]
$$

## Correctness

The first reversal places elements in reverse order. The next two reversals restore the relative order inside each rotated block:

* the first $k$ elements become the rotated prefix
* the remaining elements follow in original order

Thus the final arrangement matches rotation by $k$.

## Complexity

| operation   | time   |
| ----------- | ------ |
| rotation    | $O(n)$ |
| extra space | $O(1)$ |

All elements are moved a constant number of times.

## When to Use

Array rotation is appropriate when:

* cyclic shifts are required
* in-place transformation is preferred
* memory overhead must remain constant

It is less suitable when:

* the array must remain immutable
* repeated rotations dominate, in which case index mapping or circular buffers are better

## Implementation

```python id="array-rotation-python"
def rotate_right(a, k):
    n = len(a)
    k %= n

    def reverse(l, r):
        while l < r:
            a[l], a[r] = a[r], a[l]
            l += 1
            r -= 1

    reverse(0, n - 1)
    reverse(0, k - 1)
    reverse(k, n - 1)
```

```go id="array-rotation-go"
func RotateRight[T any](a []T, k int) {
    n := len(a)
    k %= n

    reverse := func(l, r int) {
        for l < r {
            a[l], a[r] = a[r], a[l]
            l++
            r--
        }
    }

    reverse(0, n-1)
    reverse(0, k-1)
    reverse(k, n-1)
}
```