Array Rotation: Shifting Elements Circularly
What you'll learn: How to rotate array elements left or right by k positions efficiently using the reversal algorithm and modular arithmetic.
The Core Idea
Imagine you have a row of books on a shelf. Rotating left means taking books from the left end and moving them to the right end. Rotating right does the opposite. Array rotation works the same way: elements "wrap around" circularly.
For example, rotating [1, 2, 3, 4, 5] left by 2 positions gives [3, 4, 5, 1, 2]. The first two elements moved to the end.
Two Key Techniques
1. Modular Arithmetic for Position Calculation
When rotating, each element's new position can be calculated using the modulo operator. For a left rotation by k positions:
new_index = (old_index - k) % length
For right rotation by k:
new_index = (old_index + k) % length
This handles the wrap-around automatically.
2. The Reversal Algorithm
A clever in-place method that avoids extra arrays:
- To rotate left by k positions: reverse the first k elements, reverse the remaining elements, then reverse the entire array
- To rotate right by k positions: rotate left by
(length - k)instead
Example: Rotate [1, 2, 3, 4, 5] left by 2:
- Reverse first 2:
[2, 1, 3, 4, 5] - Reverse remaining:
[2, 1, 5, 4, 3] - Reverse all:
[3, 4, 5, 1, 2]✓
This reuses your array reversal knowledge from the previous lesson!
Why It Matters
Rotation is efficient (no new arrays needed) and appears in real problems like circular buffers and scheduling algorithms.
Key Takeaway: Array rotation shifts elements circularly using modular arithmetic for indexing or the reversal algorithm for efficient in-place rotation—both preserve all elements while changing their positions.