15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Array rotation moves every value k positions with wrap-around. A right rotation brings the last k values to the front. To do it in place, reverse the whole array, then the first k values, then the remaining n - k, after setting k to k mod n. It runs in O(n) time and O(1) extra space.
| Right rotation of [1, 2, 3, 4, 5] by 2 | [4, 5, 1, 2, 3] |
|---|---|
| Normalize first | k = k mod n, only after checking n > 0 |
| Three reversals | 0..n-1, then 0..k-1, then k..n-1 |
| Time | O(n): segments of n, k and n - k total 2n |
| Extra space | O(1), one temporary per swap |
| Shifting one step k times | O(nk), the slow alternative |
The lesson uses these array skills:
left through right.We will use a nonnegative right-rotation count k.
A right rotation by k moves every value k positions to the right, wrapping values that pass the final index back to the front.
For example, rotating [1, 2, 3, 4, 5] right by 2 should produce:
1[4, 5, 1, 2, 3]The last two values become the first two values.
Use this input throughout:
1A = [1, 2, 3, 4, 5]
2rotate right by k = 2Write the indices above the values.
1index: 0 1 2 3 4
2A: [1, 2, 3, 4, 5]A direct description of the desired result is:
1original: [1, 2, 3, 4, 5]
2suffix: [4, 5]
3prefix: [1, 2, 3]
4
5result: [4, 5, 1, 2, 3]The final k values must move to the front. The remaining values retain their relative order after them.
Use one operation: reverse a segment in place.
To reverse the whole example array, start two indices at the endpoints.
1index: 0 1 2 3 4
2A: [1, 2, 3, 4, 5]
3left ^
4right ^Swap the endpoint values, then move both indices inward.
First normalize the rotation count.
The array length is 5, so:
1k = 2 mod 5 = 2The count is already within the useful range from 0 through 4.
Now perform three reversals.
Rotate right by k with three in-place reversals: reverse everything, reverse the first k, then reverse the rest. [1, 2, 3, 4, 5] with k = 2 becomes [4, 5, 1, 2, 3].
Start with left = 0 and right = 4.
1swap A[0] and A[4]
2
3before: [1, 2, 3, 4, 5]
4after: [5, 2, 3, 4, 1]
5
6left = 1, right = 3Swap the next endpoints.
1swap A[1] and A[3]
2
3before: [5, 2, 3, 4, 1]
4after: [5, 4, 3, 2, 1]
5
6left = 2, right = 2Now left >= right, so this reversal stops.
1State 1: [5, 4, 3, 2, 1]The first segment contains exactly k = 2 elements.
Swap indices 0 and 1.
1before: [5, 4, 3, 2, 1]
2after: [4, 5, 3, 2, 1]The segment is complete.
1State 2: [4, 5, 3, 2, 1]Start at indices 2 and 4.
1swap A[2] and A[4]
2
3before: [4, 5, 3, 2, 1]
4after: [4, 5, 1, 2, 3]
5
6left = 3, right = 3The pointers meet, so the reversal stops.
1State 3: [4, 5, 1, 2, 3]1[4, 5, 1, 2, 3]The result is the original array rotated right by 2.
Consider one reversal.
After swapping the values at left and right, those two values are finished. They are in the positions they occupy in the fully reversed segment.
For the full reversal of [1, 2, 3, 4, 5]:
1after first swap: [5, 2, 3, 4, 1]The values at indices 0 and 4 will not change again. Only indices 1 through 3 still need work.
The reversal invariant is:
During reversal of a segment, elements outside the active interval are already in their final reversed positions, while the active interval contains the not-yet-swapped middle portion.
The active interval begins as the whole segment. Each swap finishes two more positions. Moving left right and right left removes those finished positions from the active interval.
When left >= right, there is no unswapped endpoint pair left. For an odd-length segment, one middle value may remain. It stays in its own reversed position.
For a segment from left through right:
left < right:
left.right.The condition is strictly left < right. A pair needs two distinct positions.
Let the original nonempty array be split into:
1prefix P of length n - k
2suffix S of length kThe original order is:
1P SWe want:
1S PApply reversals:
1P S
2reverse all -> reverse(S) reverse(P)
3reverse first k -> S reverse(P)
4reverse remaining -> S PSo the segment boundaries are:
0 through n - 1.k indices: 0 through k - 1.n - k indices: k through n - 1.Normalize the count before choosing those boundaries:
1k = k mod nModulo normalization is valid only when n > 0. An empty array must return before taking a modulo.
reverseInPlace mutates values. Its left and right parameters identify a nonempty inclusive segment.
rotateRightInPlace mutates values and returns the same array reference. Its input k is nonnegative.
11 procedure reverseInPlace(values, left, right) -> values
22 // Mutates values[left..right], inclusive.
33 // Precondition: 0 <= left <= right < length(values).
44 while left < right
55 temporary <- values[left]
66 values[left] <- values[right]
77 values[right] <- temporary
88 left <- left + 1
99 right <- right - 1
1010 return values
11
1211 procedure rotateRightInPlace(values, k) -> values
1312 // Mutates values. Precondition: k >= 0.
1413 n <- length(values)
1514 if n = 0
1615 return values
1716
1817 k <- k mod n
1918 if k = 0
2019 return values
2120
2221 reverseInPlace(values, 0, n - 1)
2322 reverseInPlace(values, 0, k - 1)
2423 reverseInPlace(values, k, n - 1)
2524 return valuesNo second array of values is allocated. The temporary variable exists only long enough to complete one swap.
Run rotateRightInPlace(A, 2) with:
1A = [1, 2, 3, 4, 5]1Line 13: n <- length(A) = 5
2Line 14: n = 0 is false
3Line 17: k <- 2 mod 5 = 2
4Line 18: k = 0 is falseCall:
1reverseInPlace(A, 0, 4)1Line 4: 0 < 4 is true
2Line 5: temporary <- A[0] = 1
3Line 6: A[0] <- A[4] = 5
4Line 7: A[4] <- temporary = 1
5 A is now [5, 2, 3, 4, 1]
6Line 8: left <- 1
7Line 9: right <- 31Line 4: 1 < 3 is true
2Line 5: temporary <- A[1] = 2
3Line 6: A[1] <- A[3] = 4
4Line 7: A[3] <- temporary = 2
5 A is now [5, 4, 3, 2, 1]
6Line 8: left <- 2
7Line 9: right <- 21Line 4: 2 < 2 is false
2Line 10: return ACall:
1reverseInPlace(A, 0, 1)1Line 4: 0 < 1 is true
2Line 5: temporary <- A[0] = 5
3Line 6: A[0] <- A[1] = 4
4Line 7: A[1] <- temporary = 5
5 A is now [4, 5, 3, 2, 1]
6Line 8: left <- 1
7Line 9: right <- 01Line 4: 1 < 0 is false
2Line 10: return ACall:
1reverseInPlace(A, 2, 4)1Line 4: 2 < 4 is true
2Line 5: temporary <- A[2] = 3
3Line 6: A[2] <- A[4] = 1
4Line 7: A[4] <- temporary = 3
5 A is now [4, 5, 1, 2, 3]
6Line 8: left <- 3
7Line 9: right <- 31Line 4: 3 < 3 is false
2Line 10: return ALine 24 returns:
1Line 24: return A = [4, 5, 1, 2, 3]Consider a call that reverses an inclusive segment from left through right.
Initialization: Before the first loop iteration, no positions outside the active interval have been processed. The active interval is the entire requested segment. The reversal invariant holds.
Preservation: Suppose the invariant holds at the start of an iteration and left < right.
values[left] belongs at index right in the reversed segment.values[right] belongs at index left in the reversed segment.The newly finished endpoints are now outside the new active interval. All earlier finished positions remain unchanged. The invariant still holds.
Termination: The loop stops when left >= right. No pair of distinct active endpoints remains. Every endpoint pair has been swapped into its final reversed position. If one middle value remains, it maps to itself. Thus the segment is reversed.
For a nonempty array, line 17 replaces k with k mod n. The resulting k is in the range 0 through n - 1.
If normalized k is 0, returning unchanged is correct: a rotation by zero positions leaves every value where it is.
When k is nonzero, split the original array into a prefix P of length n - k and a suffix S of length k.
1original array: P S
2after reversing all: reverse(S) reverse(P)
3after reversing first k: S reverse(P)
4after reversing remaining: S PS P is exactly the original array rotated right by k. Since each reversal is correct, the three calls produce the required right rotation.
For an empty array, line 14 returns before line 17. The algorithm never computes k mod 0.
Reversing a segment of m elements swaps its outer pair, then its next outer pair, and continues inward.
The number of swaps is:
1floor(m / 2)Each swap performs constant work: one temporary assignment and two array writes. Therefore reversal takes:
1O(m) timeThe three reversal calls process segments of sizes:
1n
2k
3n - kTheir total processed length is:
1n + k + (n - k) = 2nSo a nonempty right rotation takes:
1O(n) timeThe algorithm stores:
n.k.These are a constant number of variables, so auxiliary space is:
1O(1)Auxiliary-space accounting excludes the input array because the algorithm mutates that existing array.
Rotating one step at a time and shifting every element for each of k steps can perform work proportional to:
1n * kThat approach can take O(nk) time.
left <= right as another endpoint pairIncorrect loop condition:
1while left <= rightExposing input:
1[1, 2, 3]After swapping indices 0 and 2, the pointers both reach index 1.
1[3, 2, 1]
2 ^
3left = right = 1A further iteration performs a self-swap at index 1. The final values happen to remain correct, but the implementation now treats one position as though it were an endpoint pair. That obscures the pair-based reasoning and performs unnecessary work.
Correction:
1while left < rightStop once the pointers meet or cross.
0 through k instead of 0 through k - 1Incorrect segment calls after reversing all:
1reverseInPlace(values, 0, k)
2reverseInPlace(values, k, n - 1)Exposing input:
1[1, 2, 3, 4, 5], k = 2After reversing all:
1[5, 4, 3, 2, 1]The incorrect first call reverses three elements, not two:
1reverse indices 0..2 -> [3, 4, 5, 2, 1]The second incorrect call overlaps at index 2:
1reverse indices 2..4 -> [3, 4, 1, 2, 5]The result is not the requested right rotation.
Correction: the first segment must contain exactly k elements.
1reverseInPlace(values, 0, k - 1)
2reverseInPlace(values, k, n - 1)Incorrect order:
1k <- k mod length(values)
2if length(values) = 0
3 return valuesExposing input:
1[], k = 2The modulo is computed with length 0, causing division or modulo by zero.
Correction: handle the empty array first.
1if length(values) = 0
2 return values
3k <- k mod length(values)Incorrect interpretation for:
1[1, 2, 3, 4, 5], k = 2A left rotation by 2 produces:
1[3, 4, 5, 1, 2]The requested right rotation is:
1[4, 5, 1, 2, 3]Correction: define the direction first. For a right rotation, the final k values move to the front, and the three reversal segments are:
10..n-1
20..k-1
3k..n-1Implement these mutating operations:
1reverseInPlace(values, left, right)
2rotateRightInPlace(values, k)The executable tests verify:
k = 0.k equal to the array length.k greater than the array length.1def reverse_in_place(values, left, right):
2 while left < right: # a pair needs two distinct positions
3 temporary = values[left]
4 values[left] = values[right]
5 values[right] = temporary
6 left += 1
7 right -= 1
8 return values
9
10def rotate_right_in_place(values, k):
11 n = len(values)
12 if n == 0: # before k % n, which would divide by zero
13 return values
14 k = k % n
15 if k == 0:
16 return values
17 reverse_in_place(values, 0, n - 1)
18 reverse_in_place(values, 0, k - 1)
19 reverse_in_place(values, k, n - 1)
20 return values
21
22print("reverse:", reverse_in_place([1, 2, 3, 4, 5], 0, 4))
23print("rotate k=2:", rotate_right_in_place([1, 2, 3, 4, 5], 2))
24print("rotate k=7:", rotate_right_in_place([1, 2, 3, 4, 5], 7))
25print("rotate [] k=2:", rotate_right_in_place([], 2))1import java.util.Arrays;
2
3public class Main {
4 static int[] reverseInPlace(int[] values, int left, int right) {
5 while (left < right) { // a pair needs two distinct positions
6 int temporary = values[left];
7 values[left] = values[right];
8 values[right] = temporary;
9 left++;
10 right--;
11 }
12 return values;
13 }
14
15 static int[] rotateRightInPlace(int[] values, int k) {
16 int n = values.length;
17 if (n == 0) return values; // before k % n, which would divide by zero
18 k = k % n;
19 if (k == 0) return values;
20 reverseInPlace(values, 0, n - 1);
21 reverseInPlace(values, 0, k - 1);
22 reverseInPlace(values, k, n - 1);
23 return values;
24 }
25
26 public static void main(String[] args) {
27 System.out.println("reverse: " + Arrays.toString(reverseInPlace(new int[]{1, 2, 3, 4, 5}, 0, 4)));
28 System.out.println("rotate k=2: " + Arrays.toString(rotateRightInPlace(new int[]{1, 2, 3, 4, 5}, 2)));
29 System.out.println("rotate k=7: " + Arrays.toString(rotateRightInPlace(new int[]{1, 2, 3, 4, 5}, 7)));
30 System.out.println("rotate [] k=2: " + Arrays.toString(rotateRightInPlace(new int[]{}, 2)));
31 }
32}1#include <iostream>
2#include <utility>
3#include <vector>
4using namespace std;
5
6void reverseInPlace(vector<int>& values, int left, int right) {
7 while (left < right) { // a pair needs two distinct positions
8 swap(values[left], values[right]);
9 left++;
10 right--;
11 }
12}
13
14void rotateRightInPlace(vector<int>& values, int k) {
15 int n = values.size();
16 if (n == 0) return; // before k % n, which would divide by zero
17 k = k % n;
18 if (k == 0) return;
19 reverseInPlace(values, 0, n - 1);
20 reverseInPlace(values, 0, k - 1);
21 reverseInPlace(values, k, n - 1);
22}
23
24void show(const char* label, const vector<int>& a, bool last = false) {
25 cout << label << "[";
26 for (size_t i = 0; i < a.size(); i++) cout << (i ? ", " : "") << a[i];
27 cout << "]" << (last ? "" : "\n");
28}
29
30int main() {
31 vector<int> a = {1, 2, 3, 4, 5};
32 reverseInPlace(a, 0, 4);
33 show("reverse: ", a);
34 a = {1, 2, 3, 4, 5};
35 rotateRightInPlace(a, 2);
36 show("rotate k=2: ", a);
37 a = {1, 2, 3, 4, 5};
38 rotateRightInPlace(a, 7);
39 show("rotate k=7: ", a);
40 a = {};
41 rotateRightInPlace(a, 2);
42 show("rotate [] k=2: ", a, true);
43 cout << endl;
44}1function reverseInPlace(values, left, right) {
2 while (left < right) { // a pair needs two distinct positions
3 const temporary = values[left];
4 values[left] = values[right];
5 values[right] = temporary;
6 left++;
7 right--;
8 }
9 return values;
10}
11
12function rotateRightInPlace(values, k) {
13 const n = values.length;
14 if (n === 0) return values; // before k % n, which would give NaN
15 k = k % n;
16 if (k === 0) return values;
17 reverseInPlace(values, 0, n - 1);
18 reverseInPlace(values, 0, k - 1);
19 reverseInPlace(values, k, n - 1);
20 return values;
21}
22
23const show = (a) => `[${a.join(', ')}]`;
24console.log(`reverse: ${show(reverseInPlace([1, 2, 3, 4, 5], 0, 4))}`);
25console.log(`rotate k=2: ${show(rotateRightInPlace([1, 2, 3, 4, 5], 2))}`);
26console.log(`rotate k=7: ${show(rotateRightInPlace([1, 2, 3, 4, 5], 7))}`);
27console.log(`rotate [] k=2: ${show(rotateRightInPlace([], 2))}`);Put one index at each end. While left < right, swap the two values and move both indices inward. That is floor(n / 2) swaps in O(n) time and O(1) space. Write this loop yourself for an int[]; Collections.reverse only accepts a list.
Split the array into a prefix P of length n - k and a suffix S of length k, so it reads P S. Reversing everything gives reverse(S) reverse(P). Reversing each part back gives S P, which is the right rotation.
O(n) time and O(1) extra space with three reversals. The segments have sizes n, k and n - k, which add up to 2n work. Moving every value one step, k times, costs O(nk).
Replace k with k mod n first. Rotating a 5-element array by 7 equals rotating it by 2. Check for an empty array before the modulo, because k mod 0 divides by zero.
Direction decides which values wrap. Rotating [1, 2, 3, 4, 5] left by 2 gives [3, 4, 5, 1, 2], while right by 2 gives [4, 5, 1, 2, 3]. A left rotation by k equals a right rotation by n - k.