101
0/276
Loading content...
Array rotation and reversal are among the most fundamental operations in array manipulation. They appear everywhere—from implementing circular buffers and image processing to solving interview classics like rotating a matrix or the "rotate string" problem.
These operations are deceptively simple to describe but reveal surprising depth when you pursue optimal solutions. The journey from a naive O(n²) rotation to an elegant O(n) in-place algorithm demonstrates key algorithmic insights:
Mastering these transformations builds intuition that transfers to many other problems.
By the end of this page, you will understand array reversal in-place, multiple approaches to array rotation (extra space, cycle, reversal), the mathematical foundations behind rotation cycles, and when to apply each technique based on constraints.
Array reversal transforms [a, b, c, d, e] into [e, d, c, b, a]. It's the simpler of our two operations and serves as a building block for the elegant rotation algorithm we'll develop.
The Two-Pointer Approach:
The optimal in-place reversal uses two pointers starting at opposite ends, swapping elements as they move toward each other. When the pointers meet or cross, we're done.
1234567891011121314151617181920212223242526272829
/** * Reverse an array in-place using two pointers. * * Time Complexity: O(n) — each element visited once * Space Complexity: O(1) — only swap variable needed * * Swaps: Exactly ⌊n/2⌋ swaps */function reverseArray(arr: number[]): void { let left = 0; let right = arr.length - 1; while (left < right) { // Swap elements at left and right pointers [arr[left], arr[right]] = [arr[right], arr[left]]; left++; right--; }} // Exampleconst arr = [1, 2, 3, 4, 5];reverseArray(arr);console.log(arr); // [5, 4, 3, 2, 1] // Works for even and odd length arraysconst even = [1, 2, 3, 4];reverseArray(even);console.log(even); // [4, 3, 2, 1]Reversing a Range:
Often we need to reverse only a portion of an array. The same logic applies with adjusted boundaries:
1234567891011121314151617
/** * Reverse elements in array from index 'start' to 'end' (inclusive). * Modifies array in-place. */function reverseRange(arr: number[], start: number, end: number): void { while (start < end) { [arr[start], arr[end]] = [arr[end], arr[start]]; start++; end--; }} // Example: Reverse middle portionconst arr = [1, 2, 3, 4, 5, 6, 7];reverseRange(arr, 2, 5);console.log(arr); // [1, 2, 6, 5, 4, 3, 7]// ^^^^^^^^ reversedThink of reverseRange() as a reusable primitive. Once you have it, more complex transformations become compositions of reversals—a powerful pattern we'll exploit for rotation.
Array rotation shifts all elements by k positions, with elements that "fall off" one end reappearing at the other. There are two directions:
Right Rotation (Clockwise):
[1, 2, 3, 4, 5] rotated right by 2 → [4, 5, 1, 2, 3]
Each element moves k positions to the right. The last k elements wrap to the front.
Left Rotation (Counter-clockwise):
[1, 2, 3, 4, 5] rotated left by 2 → [3, 4, 5, 1, 2]
Each element moves k positions to the left. The first k elements wrap to the back.
Key Relationship:
Rotating by n positions returns the array to its original state. Thus, rotation by k is equivalent to rotation by (k mod n). Always normalize k before processing: k = k % n. If k becomes 0, no rotation is needed.
Applications of Rotation:
The most straightforward approach uses an auxiliary array to hold elements during rotation. It's easy to understand and implement, trading O(n) space for simplicity.
1234567891011121314151617181920212223242526272829303132
/** * Rotate array right by k positions using extra space. * * Time Complexity: O(n) * Space Complexity: O(n) — extra array of size n */function rotateWithExtraArray(nums: number[], k: number): void { const n = nums.length; if (n === 0) return; k = k % n; // Normalize k if (k === 0) return; // Create result array const rotated = new Array(n); // Place each element in its new position for (let i = 0; i < n; i++) { const newPosition = (i + k) % n; rotated[newPosition] = nums[i]; } // Copy back to original array for (let i = 0; i < n; i++) { nums[i] = rotated[i]; }} // Example: Right rotation by 2const arr = [1, 2, 3, 4, 5];rotateWithExtraArray(arr, 2);console.log(arr); // [4, 5, 1, 2, 3]Visualization:
Original: [1, 2, 3, 4, 5]
Rotate right by k=2:
Element at index 0 → index (0+2)%5 = 2: rotated[2] = 1
Element at index 1 → index (1+2)%5 = 3: rotated[3] = 2
Element at index 2 → index (2+2)%5 = 4: rotated[4] = 3
Element at index 3 → index (3+2)%5 = 0: rotated[0] = 4
Element at index 4 → index (4+2)%5 = 1: rotated[1] = 5
Result: [4, 5, 1, 2, 3]
A naive in-place approach rotates the array by one position, k times. This uses O(1) space but has poor time complexity.
1234567891011121314151617181920212223242526272829303132333435363738
/** * Rotate array right by 1 position. * Save last element, shift everything right, place saved at front. * * Time: O(n) for one rotation */function rotateByOne(nums: number[]): void { if (nums.length <= 1) return; const last = nums[nums.length - 1]; // Shift all elements one position to the right for (let i = nums.length - 1; i > 0; i--) { nums[i] = nums[i - 1]; } nums[0] = last;} /** * Rotate array right by k positions by rotating one-by-one. * * Time Complexity: O(n × k) — terrible for large k! * Space Complexity: O(1) */function rotateOneByOne(nums: number[], k: number): void { const n = nums.length; k = k % n; for (let i = 0; i < k; i++) { rotateByOne(nums); }} // Exampleconst arr = [1, 2, 3, 4, 5];rotateOneByOne(arr, 2);console.log(arr); // [4, 5, 1, 2, 3]This approach has O(n × k) time complexity—O(n²) in the worst case when k ≈ n/2. For a million-element array rotated by 500,000 positions, this means 500 billion operations. Never use this approach for performance-critical code.
Why mention this approach?
The cyclic replacement approach is mathematically elegant. It follows each element to its destination, then follows the displaced element to its destination, continuing until we complete a cycle. Some arrays complete in one cycle; others require multiple.
The Key Insight:
When we rotate, each element eventually returns to its starting position after being displaced n/gcd(n,k) times. The array partitions into exactly gcd(n,k) independent cycles.
1234567891011121314151617181920212223242526272829303132333435363738394041424344
/** * Rotate array using cyclic replacement. * * Key insight: Elements form cycles when rotated. * Number of cycles = gcd(n, k) * Elements per cycle = n / gcd(n, k) * * Time Complexity: O(n) — each element moved exactly once * Space Complexity: O(1) — only temp variable needed */function rotateCyclic(nums: number[], k: number): void { const n = nums.length; k = k % n; if (k === 0 || n <= 1) return; let count = 0; // Track total elements moved for (let start = 0; count < n; start++) { let current = start; let prev = nums[start]; do { // Calculate next position in the cycle const next = (current + k) % n; // Save element at next position const temp = nums[next]; // Place previous element at next position nums[next] = prev; // Move forward in cycle prev = temp; current = next; count++; } while (current !== start); // Until we complete the cycle }} // Example trace for [1,2,3,4,5,6], k=2:// Cycle 1: 0→2→4→0 (moves elements 1,3,5)// Cycle 2: 1→3→5→1 (moves elements 2,4,6)// Result: [5,6,1,2,3,4]Mathematical Foundation:
Let's understand why this works.
Starting at index i, repeated rotation by k positions follows the sequence:
i → (i+k) → (i+2k) → (i+3k) → ... (all mod n)
This sequence returns to i when i + m×k ≡ i (mod n), i.e., when m×k is divisible by n.
The smallest such m is n/gcd(n,k). This is the cycle length.
Since each cycle has n/gcd(n,k) elements, and the array has n elements, we have exactly gcd(n,k) cycles.
Example: n=6, k=2
When gcd(n,k) = 1, there's exactly one cycle covering all elements—the simple case. When gcd(n,k) > 1, multiple starting points are needed. The outer loop handles this by starting new cycles until all n elements are processed.
The reversal algorithm is perhaps the most elegant solution. It achieves O(n) time and O(1) space by composing three simple reversals—no tracking of cycles, no modular arithmetic during execution.
The Key Insight:
A right rotation by k can be achieved by:
Magically, this produces the correct rotation!
12345678910111213141516171819202122232425262728293031323334353637383940
/** * Rotate array right by k positions using three reversals. * * The magic: reverse(reverse(A) reverse(B)) = B A * * Time Complexity: O(n) — each element visited at most twice * Space Complexity: O(1) — in-place swaps only */function rotateByReversal(nums: number[], k: number): void { const n = nums.length; k = k % n; if (k === 0 || n <= 1) return; // Helper to reverse a range in-place const reverse = (start: number, end: number): void => { while (start < end) { [nums[start], nums[end]] = [nums[end], nums[start]]; start++; end--; } }; // Step 1: Reverse entire array reverse(0, n - 1); // Step 2: Reverse first k elements reverse(0, k - 1); // Step 3: Reverse remaining n-k elements reverse(k, n - 1);} // Example walkthrough: [1,2,3,4,5], k=2//// Original: [1, 2, 3, 4, 5]// After reverse all: [5, 4, 3, 2, 1]// After reverse 0..1: [4, 5, 3, 2, 1] (first k=2 elements)// After reverse 2..4: [4, 5, 1, 2, 3] (remaining n-k=3 elements)//// Result: [4, 5, 1, 2, 3] ✓Why Does This Work?
Let's prove it mathematically. Denote the array as two parts:
Original array: AB Goal (right rotation by k): BA
The Reversal Magic:
Result: BA — exactly what we wanted!
This works because reversing a reversed sequence gives back the original: (Xᴿ)ᴿ = X
The reversal algorithm embodies the principle of composing simple primitives into powerful operations. Three reversals—each trivial to implement and verify—combine to solve what initially seems like a complex rearrangement problem. This is algorithmic elegance at its finest.
Left Rotation Using Reversals:
For left rotation by k, simply adjust which parts you reverse:
Or equivalently, right-rotate by (n-k).
| Approach | Time | Space | Complexity | Best For |
|---|---|---|---|---|
| Extra Array | O(n) | O(n) | Simple | When space isn't constrained |
| One-by-One | O(n×k) | O(1) | Simple | Never (educational only) |
| Cyclic | O(n) | O(1) | Moderate | Understanding math structure |
| Reversal | O(n) | O(1) | Simple | Production code (recommended) |
Recommendation:
For most situations, the reversal algorithm is the best choice:
The cyclic approach is worth understanding for its mathematical elegance and for problems where you need to track the cycle structure itself. The extra array approach is fine when O(n) space is acceptable and code simplicity is paramount.
In interviews, mention you know multiple approaches. Start with the simple extra-space solution, then optimize to the reversal algorithm. This shows both problem-solving progression and awareness of space-time tradeoffs.
Rotation and reversal patterns appear in many classic problems. Here are some important applications:
1234
function rotateString(s: string, goal: string): boolean { if (s.length !== goal.length) return false; return (s + s).includes(goal);}123456789101112131415161718192021222324
/** * Rotate n×n matrix 90° clockwise in-place. * Method: Transpose, then reverse each row. */function rotateMatrix(matrix: number[][]): void { const n = matrix.length; // Transpose (swap across diagonal) for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]]; } } // Reverse each row for (let i = 0; i < n; i++) { matrix[i].reverse(); }} // Example:// [[1,2,3], Transpose [[1,4,7], Reverse rows [[7,4,1],// [4,5,6], ────────────> [2,5,8], ────────────> [8,5,2],// [7,8,9]] [3,6,9]] [9,6,3]]Array rotation and reversal are fundamental transformations that appear throughout algorithm design. Let's consolidate the key insights:
What's Next:
With rotation and reversal mastered, we continue building our array pattern library. The next page covers merging sorted arrays—a fundamental operation that forms the backbone of merge sort and appears in countless interview and production scenarios.
Reversal and rotation patterns are now part of your toolkit. The reversal trick—composing simple operations into complex transformations—is a meta-pattern that applies far beyond arrays. Look for opportunities to decompose complex operations into sequences of simpler, well-understood primitives.