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:

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

Rotate it left by 3 positions:

[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:

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

For example:

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

Rotate left by 3.

First reverse the prefix:

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

Then reverse the suffix:

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

Then reverse the whole array:

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

Implementation

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.

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:

[1, 2, 3, 4, 5]

Rotating right by 2 gives:

[4, 5, 1, 2, 3]

Why Three Reversals Work

Write the array as a concatenation of two blocks:

A = X Y

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

A left rotation by k should produce:

Y X

The three reversal method does this:

reverse(X) reverse(Y)

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

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:

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.

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:

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).

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:

O(n)

Extra space:

O(1)

The copy method costs:

O(n)

time and:

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:

k %= n

A negative rotation can be normalized with:

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.