# 2.7 Rotation

Array rotation moves elements by a fixed offset while preserving their relative circular order. A left rotation by `k` moves each element at index `i` to index `i - k` modulo `n`. A right rotation by `k` moves each element at index `i` to index `i + k` modulo `n`.

Rotation appears in cyclic buffers, scheduling, string matching, block rearrangement, and in-place array transformations.

## Problem

Given an array:

```text
[1, 2, 3, 4, 5, 6, 7]
```

Rotate it left by `3` positions:

```text
[4, 5, 6, 7, 1, 2, 3]
```

A direct implementation copies elements into a new array. That is simple, but it uses `O(n)` extra space. The goal is to rotate in place using `O(1)` extra space.

## Solution: Three Reversals

A left rotation by `k` can be implemented by reversing three ranges:

```text
reverse A[0:k]
reverse A[k:n]
reverse A[0:n]
```

For example:

```text
[1, 2, 3, 4, 5, 6, 7]
```

Rotate left by `3`.

First reverse the prefix:

```text
[3, 2, 1, 4, 5, 6, 7]
```

Then reverse the suffix:

```text
[3, 2, 1, 7, 6, 5, 4]
```

Then reverse the whole array:

```text
[4, 5, 6, 7, 1, 2, 3]
```

## Implementation

```go
func RotateLeft(a []int, k int) {
	n := len(a)
	if n == 0 {
		return
	}

	k %= n
	if k < 0 {
		k += n
	}

	reverse(a, 0, k)
	reverse(a, k, n)
	reverse(a, 0, n)
}

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

The helper `reverse(a, l, r)` reverses the half-open range `[l, r)`. This convention avoids special cases and matches Go slice notation.

## Right Rotation

A right rotation by `k` is the same as a left rotation by `n - k`.

```go
func RotateRight(a []int, k int) {
	n := len(a)
	if n == 0 {
		return
	}

	k %= n
	if k < 0 {
		k += n
	}

	RotateLeft(a, n-k)
}
```

For example:

```text
[1, 2, 3, 4, 5]
```

Rotating right by `2` gives:

```text
[4, 5, 1, 2, 3]
```

## Why Three Reversals Work

Write the array as a concatenation of two blocks:

```text
A = X Y
```

where `X = A[0:k]` and `Y = A[k:n]`.

A left rotation by `k` should produce:

```text
Y X
```

The three reversal method does this:

```text
reverse(X) reverse(Y)
```

Then reversing the whole array reverses the order of the blocks and reverses each block internally again:

```text
reverse(reverse(X) reverse(Y)) = Y X
```

Thus the final array is exactly the left rotation.

## Invariant for Reversal

The reversal helper maintains this invariant:

```text
At the start of each iteration, all elements outside the current range [l, r) have already been placed in their final reversed positions.
```

Each step swaps the first and last unprocessed elements, then shrinks the unprocessed range. When `l >= r - 1`, there are no remaining pairs to swap.

## Alternative: Extra Array

The simplest implementation uses a second array.

```go
func RotateLeftCopy(a []int, k int) []int {
	n := len(a)
	if n == 0 {
		return nil
	}

	k %= n
	if k < 0 {
		k += n
	}

	out := make([]int, n)
	for i := 0; i < n; i++ {
		out[i] = a[(i+k)%n]
	}

	return out
}
```

This version is often preferable when immutability matters, when the original array must be preserved, or when clarity matters more than memory usage.

## Alternative: Juggling Method

The juggling method rotates elements by following cycles induced by the mapping:

```text
i -> (i - k) mod n
```

For a left rotation by `k`, each element moves to index `(i - k + n) % n`.

The number of cycles is `gcd(n, k)`.

```go
func RotateLeftJuggle(a []int, k int) {
	n := len(a)
	if n == 0 {
		return
	}

	k %= n
	if k < 0 {
		k += n
	}

	g := gcd(n, k)

	for start := 0; start < g; start++ {
		tmp := a[start]
		i := start

		for {
			j := i + k
			if j >= n {
				j -= n
			}

			if j == start {
				break
			}

			a[i] = a[j]
			i = j
		}

		a[i] = tmp
	}
}

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}
```

This method also uses `O(1)` extra space and `O(n)` time. It is useful when you want to reason directly about index cycles, but the reversal method is usually easier to read.

## Complexity

The three-reversal method reverses each element at most twice.

Time complexity:

```text
O(n)
```

Extra space:

```text
O(1)
```

The copy method costs:

```text
O(n)
```

time and:

```text
O(n)
```

extra space.

## Boundary Conditions

An empty array must be handled before computing `k % n`, because division by zero is invalid.

A rotation by `0` leaves the array unchanged.

A rotation by `n` leaves the array unchanged.

A rotation by a value larger than `n` should be reduced with:

```go
k %= n
```

A negative rotation can be normalized with:

```go
if k < 0 {
	k += n
}
```

After normalization, `0 <= k < n`.

## Common Pitfalls

Forgetting to normalize `k` causes out-of-range slice access.

Computing `k % n` before checking `n == 0` causes a runtime panic.

Confusing left rotation with right rotation reverses the result.

Using inclusive ranges inside a helper designed for half-open ranges causes off-by-one errors.

The juggling method is easy to get wrong because the saved temporary value must be written back exactly when the cycle closes.

## Takeaway

Rotation is circular movement of elements. For most in-place code, use the three-reversal method: reverse the prefix, reverse the suffix, then reverse the whole array. It is linear, constant space, and easier to verify than cycle-based implementations.