Why this matters
A rotation moves every value in an array a fixed number of places, and the values that fall off one end come back in at the other end. Any program that keeps a list in a circle, such as a row of tiles that slides around, needs this move. The question is how to do it without wasting memory.
The obvious method copies the values into a second array in their new order. That works, but it needs a second array as large as the first. When the array is a million numbers, you pay for a second million numbers. The method in this lesson does the job by reversing parts of the array in place, so it needs only a few index variables.
This lesson uses only the array itself and the standard function std::reverse. The neighbouring lessons cover sliding windows, the difference trick that applies many updates at once, and the matrix rotation that turns a grid. Here the topic is the one-dimensional rotation of a single row of values.
The idea: rotate means move a block to the front
Start with a concrete case. The array holds the values 1 2 3 4 5 6 7, and you want to rotate it right by 3. Rotating right means every value moves three places toward the end. The last three values, 5 6 7, wrap around to the front. The rest, 1 2 3 4, follow them. The result is:
before: 1 2 3 4 5 6 7
after: 5 6 7 1 2 3 4Split the array into two blocks. Block A is the first n - k values, here 1 2 3 4. Block B is the last k values, here 5 6 7. The rotated array is block B followed by block A. Your job is to swap the two blocks without a second array.
Think of a row of people in a queue. You want the last three people to walk to the front and keep their order, and the first four to stand behind them in their order. Reversing a line is an easy job to describe: the first person becomes the last, the second becomes the second to last, and so on. Reversing is also easy to do in place, meaning you swap pairs of values inside the same array.
Reversing a range
The function std::reverse takes two iterators and reverses the values between them. An iterator is a small object that points at one position in a container. The first iterator points at the first value you want to reverse. The second iterator points one place past the last value. Writing a.end() as the second argument means "up to the end", and this past-the-end rule is the reason many beginners make mistakes, as shown in the Common mistakes section.
Here is the smallest example. It reverses the whole array and then prints it.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> a = {1, 2, 3, 4, 5};
reverse(a.begin(), a.end());
for (int x : a) {
cout << x << ' ';
}
cout << '\n';
return 0;
}Its output is:
5 4 3 2 1 The header <algorithm> brings in reverse. The header <iostream> gives cout, and <vector> gives vector. The line using namespace std; lets you write reverse instead of std::reverse. Beginners often see this line in tutorials. It is common in short teaching programs, and larger projects usually write std:: in front of each name instead.
The loop for (int x : a) is a range-based for loop. It visits each value of a in order and copies it into x, one at a time. It does not change a.
Reversing a part of an array uses the same function with different iterators. The call reverse(a.begin(), a.begin() + 3) reverses only the first three values, because a.begin() + 3 points at position 3, which is the fourth value, and the range stops before it. Position 3 is not touched.
The three reversals
Now the trick. Start again with 1 2 3 4 5 6 7 and k = 3. The method has three steps, and this list shows the array after each one:
- Reverse the whole array. The values 1 to 7 become 7 6 5 4 3 2 1.
- Reverse the first
kvalues, which are 7 6 5. They become 5 6 7. The array is now 5 6 7 4 3 2 1. - Reverse the rest, the values after the first
k. These are 4 3 2 1, which become 1 2 3 4. The array is now 5 6 7 1 2 3 4.
The program below prints the array after each step, so you can check the claim yourself. It is a trace, which means a record of each step as the program runs.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
void show(const char* label, const vector<int>& a) {
cout << label << ":";
for (int x : a) {
cout << ' ' << x;
}
cout << '\n';
}
int main() {
vector<int> a = {1, 2, 3, 4, 5, 6, 7};
int k = 3;
show("start ", a);
reverse(a.begin(), a.end());
show("reverse all ", a);
reverse(a.begin(), a.begin() + k);
show("reverse first k ", a);
reverse(a.begin() + k, a.end());
show("reverse the rest ", a);
return 0;
}Its output is:
start : 1 2 3 4 5 6 7
reverse all : 7 6 5 4 3 2 1
reverse first k : 5 6 7 4 3 2 1
reverse the rest : 5 6 7 1 2 3 4The function show takes a label and the array, and prints both. Its first parameter is a const char*, which is a plain piece of text. The second parameter is const vector<int>&. The & means the function receives the array itself, not a copy, and const promises the function will not change it. Passing a large array by reference costs almost nothing, because only the address is passed.
Why it works
You can check the trick with a short argument, without the trace. Call the first block A and the second block B. The array starts as A followed by B. Reversing a whole array turns X Y into the reverse of Y followed by the reverse of X. So reversing A B gives rev(B) rev(A). Block B is now at the front, but each block is backwards. The first k values are rev(B), which has length k. Reversing the first k values turns rev(B) back into B. Reversing the rest turns rev(A) back into A. The final array is B followed by A, which is the rotation.
The reversal of a whole array is the step that moves the blocks. The two partial reversals undo the backwards order that the whole reversal caused. Nothing else is needed.
Writing the function
Put the three steps into a function. It takes the array by reference, so the caller's array changes, and it takes the number of steps k.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
void rotateRight(vector<int>& a, int k) {
int n = static_cast<int>(a.size());
if (n == 0) {
return;
}
k %= n;
reverse(a.begin(), a.end());
reverse(a.begin(), a.begin() + k);
reverse(a.begin() + k, a.end());
}
void printVector(const vector<int>& a) {
for (int x : a) {
cout << x << ' ';
}
cout << '\n';
}
int main() {
vector<int> a = {1, 2, 3, 4, 5, 6, 7};
rotateRight(a, 3);
printVector(a);
return 0;
}Its output is:
5 6 7 1 2 3 4 Three details matter here.
The line int n = static_cast<int>(a.size()); stores the length as an int. The function size() returns an unsigned type, a whole-number type that cannot hold negative values. Using an int makes the arithmetic with k simpler. The static_cast<int> tells the compiler that the conversion is intended.
The check if (n == 0) returns early for an empty array. Without it, the line k %= n would divide by zero.
The line k %= n; is the step that handles large k. The symbol % gives the remainder after division. Rotating a 5-value array by 5 steps returns the same array, and rotating by 7 steps is the same as rotating by 2 steps, because 7 % 5 is 2. Without this line, a k larger than n would ask the reversal to reach past the end of the array.
Second example: k is 0, equal to n, or larger than n
The next program tests three cases that often break a first version of the code. It rotates an array of five values by 0, by 5, and by 7. It also compares the result with the standard library function std::rotate, which does a rotation in place. In real work you would call std::rotate directly, but writing your own version teaches you the method.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
void rotateRight(vector<int>& a, int k) {
int n = static_cast<int>(a.size());
if (n == 0) {
return;
}
k %= n;
reverse(a.begin(), a.end());
reverse(a.begin(), a.begin() + k);
reverse(a.begin() + k, a.end());
}
void printVector(const vector<int>& a) {
for (int x : a) {
cout << x << ' ';
}
cout << '\n';
}
int main() {
vector<int> b = {1, 2, 3, 4, 5};
rotateRight(b, 0);
printVector(b);
rotateRight(b, 5);
printVector(b);
rotateRight(b, 7);
printVector(b);
vector<int> c = {10, 20, 30, 40, 50, 60};
vector<int> d = c;
rotate(d.begin(), d.begin() + (d.size() - 2), d.end());
rotateRight(c, 2);
cout << (c == d ? "matches std::rotate" : "differs") << '\n';
printVector(c);
return 0;
}Its output is:
1 2 3 4 5
1 2 3 4 5
4 5 1 2 3
matches std::rotate
50 60 10 20 30 40 Rotating by 0 changes nothing, and rotating by 5 on five values also changes nothing, because a full turn returns every value to its place. Rotating by 7 is the same as rotating by 2 on five values, which moves 4 5 to the front.
The call rotate(d.begin(), d.begin() + (d.size() - 2), d.end()) makes the new first position the one that is two places from the end. That moves the last two values to the front, which is a right rotation by 2. The line c == d compares the two vectors value by value and returns true when they match.
Third example: rotating left
A left rotation moves every value toward the front, and the values at the front wrap around to the end. Rotating left by k is the same as rotating right by n - k. A left rotation by 2 on seven values gives the same result as a right rotation by 5. The function below uses that fact. It takes k % n first, so that the subtraction never goes below zero, and then it takes % n again so that a k of 0 gives a right rotation by 0 rather than by n.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
void rotateRight(vector<int>& a, int k) {
int n = static_cast<int>(a.size());
if (n == 0) {
return;
}
k %= n;
reverse(a.begin(), a.end());
reverse(a.begin(), a.begin() + k);
reverse(a.begin() + k, a.end());
}
void rotateLeft(vector<int>& a, int k) {
int n = static_cast<int>(a.size());
if (n == 0) {
return;
}
rotateRight(a, (n - k % n) % n);
}
void printVector(const vector<int>& a) {
for (int x : a) {
cout << x << ' ';
}
cout << '\n';
}
int main() {
vector<int> a = {1, 2, 3, 4, 5, 6, 7};
rotateLeft(a, 2);
printVector(a);
vector<int> b = {1, 2, 3, 4, 5, 6, 7};
rotateLeft(b, 9);
printVector(b);
return 0;
}Its output is:
3 4 5 6 7 1 2
3 4 5 6 7 1 2 The second call uses k = 9. Since 9 % 7 is 2, the result matches the first call. The function rotateLeft does not repeat the three steps. It reuses rotateRight with a different count, so there is one piece of logic to test.
Fourth example: one step
The smallest useful case is k = 1, which moves only the last value to the front. It is a good check because the first reversal covers a single value and does nothing. The trace below uses four values, 1 2 3 4.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
void show(const char* label, const vector<int>& a) {
cout << label << ":";
for (int x : a) {
cout << ' ' << x;
}
cout << '\n';
}
int main() {
vector<int> a = {1, 2, 3, 4};
int k = 1;
reverse(a.begin(), a.end());
show("reverse all ", a);
reverse(a.begin(), a.begin() + k);
show("reverse first", a);
reverse(a.begin() + k, a.end());
show("reverse rest ", a);
return 0;
}Its output is:
reverse all : 4 3 2 1
reverse first: 4 3 2 1
reverse rest : 4 1 2 3Reversing a single value leaves it where it is, so the second line of output matches the first. The third step then reverses the three values 3 2 1 into 1 2 3, and the result 4 1 2 3 is the array rotated right by one. The same pattern holds for any k: a one-value reversal is a no-op, and a reversal of the rest puts the other values in order.
How much work it takes
Reversing m values swaps about m / 2 pairs. The method reverses the whole array, which is n values, then the first k values, then the remaining n - k values. Together those are about n / 2 + k / 2 + (n - k) / 2, which is about n swaps. Doubling n roughly doubles the work, so the time is proportional to n. Computer scientists write this as O(n), read as "order n". The memory used is the same whatever n is, because the function only stores n, k, and the loop positions inside reverse. That is O(1) extra space, read as "constant extra space".
Copying into a second array takes the same O(n) time but O(n) extra space. The reversal method trades a few more passes over the data for not needing that second array.
Common mistakes
Forgetting to reduce k
When k is bigger than n, the iterator a.begin() + k points past the end of the array. The program then reads and writes memory that does not belong to the vector. This is undefined behaviour, which in plain words means the language makes no promise about what happens. Your program may crash, produce wrong values, or appear to work until a later change.
The program below leaves out k %= n and rotates a five-value array by 7:
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
void rotateNoMod(vector<int>& a, int k) {
reverse(a.begin(), a.end());
reverse(a.begin(), a.begin() + k);
reverse(a.begin() + k, a.end());
}
int main() {
vector<int> a = {1, 2, 3, 4, 5};
rotateNoMod(a, 7);
for (int x : a) {
cout << x << ' ';
}
cout << '\n';
return 0;
}On the g++ 15.2 build used for this lesson, the program stopped with this message:
Fatal glibc error: malloc.c:2371 (sysmalloc): assertion failedThe text after assertion failed is longer in the real output, and it names the memory allocator. The message changes between systems. The lesson for you is the cause: the iterator went past the end. Keep the line k %= n, and check the length before any reversal.
Treating the end iterator as the last value
The second iterator of reverse points one place past the last value, not at it. A common slip is to write a.end() - 1 to mean "the last value". That leaves the last value outside the range.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> b = {1, 2, 3, 4, 5};
reverse(b.begin(), b.end() - 1);
for (int x : b) {
cout << x << ' ';
}
cout << '\n';
return 0;
}Its output is:
4 3 2 1 5 The value 5 never moved. The fix is reverse(b.begin(), b.end()), which covers all five values. Read every iterator pair as "start at the first value, stop before the second one".
Splitting at the wrong place
The three reversals must split the array at position k, which is the length of block B. If you split at n - k instead, the result is the array rotated the other way by a different amount. The next program shows this with the same whole reversal and the wrong split.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> c = {1, 2, 3, 4, 5, 6, 7};
int n = static_cast<int>(c.size());
int k = 3;
reverse(c.begin(), c.end());
reverse(c.begin(), c.begin() + (n - k));
reverse(c.begin() + (n - k), c.end());
for (int x : c) {
cout << x << ' ';
}
cout << '\n';
return 0;
}Its output is:
4 5 6 7 1 2 3 That is a rotation by 4 to the right, not by 3. The call asked for 3 steps, and the program gave a different answer with no error message. Wrong results are harder to spot than crashes, so test small cases by hand, as the trace in The three reversals section does.
Calling the function with too few arguments
The function needs both the array and the step count. Leaving out one argument is a compile error, which means the compiler refuses to build the program. The following program is missing k:
#include <vector>
using namespace std;
void rotateRight(vector<int>& a, int k);
int main() {
vector<int> a = {1, 2, 3};
rotateRight(a);
return 0;
}Compiling it with g++ -std=c++20 -Wall gives:
mistake_call.cpp: In function ‘int main()’:
mistake_call.cpp:8:16: error: too few arguments to function ‘void rotateRight(std::vector<int>&, int)’
8 | rotateRight(a);
| ~~~~~~~~~~~^~~
mistake_call.cpp:4:6: note: declared here
4 | void rotateRight(vector<int>& a, int k);
| ^~~~~~~~~~~Read the first error: line. It names the function and says what the compiler expected. The note: declared here line shows where the function's parameters are written, so you can compare the two.
Practice
Exercise 1: rotate left by hand
The array is 10 20 30 40 50. Rotate it left by 1 and write the result.
Show the answer
The result is 20 30 40 50 10. A left rotation by 1 moves the first value to the end. Rotating left by 1 equals rotating right by 4, which gives the same array.
Exercise 2: predict a large k
Use rotateRight on the array 1 2 3 4 5 with k = 12. Write the array after the call.
Show the answer
The result is 4 5 1 2 3. Since 12 % 5 is 2, the call is the same as a right rotation by 2. Right by 2 moves the last two values, 4 and 5, to the front.
Exercise 3: why the split uses k
In the three-reversal method, the middle step reverses the first k values. Explain in one or two sentences why the split must be at k and not at k + 1.
Show the answer
Block B, the last k values, is what must move to the front. If the first reversal covers k + 1 values, it takes one value from block A as well, and that value ends up in the wrong place. The split at k makes the first reversal cover exactly block B.
Exercise 4: count the swaps
The function reverse swaps pairs of values. For an array of 10 values, how many swaps does the whole reversal take, and how many does the function use in total for k = 4? Assume each reversal swaps half its length, rounded down.
Show the answer
The whole reversal covers 10 values and does 5 swaps. The first reversal covers 4 values and does 2 swaps. The rest covers 6 values and does 3 swaps. The total is 5 + 2 + 3 = 10 swaps.
Summary
- A rotation by
kmoves the lastkvalues to the front and keeps their order. - Reverse the whole array, then reverse the first
kvalues, then reverse the rest. This gives the rotation with no second array. - Reduce
kwithk %= nfirst, and return early for an empty array. - The second iterator of
reversepoints one past the last value, soend()is correct andend() - 1is not. - The method takes about
nswaps and uses constant extra space. - In real code,
std::rotatedoes the same job and is the library choice.