Problem overview
The function rotate receives a vector of integers, nums, and moves every element one position to the right. The last element wraps around to the front. The change must happen in the vector itself, with no second array, so the extra space is O(1).
For [1, 2, 3, 4, 5] the result is [5, 1, 2, 3, 4]. For [4, -2, 13, 1] it is [1, 4, -2, 13]. The function returns nothing: the caller sees the change because nums is passed by reference.
Approach: save the last element, shift the rest
Every element except the last moves one slot right, and the last one goes to index 0. Writing nums[i] = nums[i - 1] for each i does the shifting, but it overwrites the old nums[i]. That value must not be lost before it is used.
The last element is the only one that would be destroyed without ever being copied elsewhere, because the first write, to index n - 1, overwrites it. So the plan is:
- save the last element in a variable;
- shift the others right, starting from the right end;
- put the saved value at index 0.
The direction of the shift matters. Going right to left, each step reads nums[i - 1], which no earlier step has touched yet. Going left to right would copy nums[0] into nums[1], then copy that same value into nums[2], and fill the vector with copies of the first element.
Step by step
- Record the size and the last value. Store
nums.size()in anintnamedn, and copynums[n - 1]intolast. - Loop from the right. Let
istart atn - 1and run whilei > 0, decreasing each time. The loop stops before index 0, which has no left neighbour to copy from. - Shift. Assign
nums[i] = nums[i - 1]. Each element moves one slot right, and the value read has not been overwritten yet. - Wrap around. After the loop, index 0 still holds its old value, which has already been copied to index 1. Assign
lasttonums[0].
The solution in C++
class Solution {
public:
void rotate(vector<int>& nums) {
int n = nums.size();
int last = nums[n - 1];
for (int i = n - 1; i > 0; i--) {
nums[i] = nums[i - 1];
}
nums[0] = last;
}
};
Tracing [1, 2, 3, 4, 5]: last is 5. The loop produces [1, 2, 3, 4, 4], then [1, 2, 3, 3, 4], then [1, 2, 2, 3, 4], then [1, 1, 2, 3, 4]. Finally nums[0] = 5 gives [5, 1, 2, 3, 4].
The C++ details worth knowing:
- Reference parameter.
vector<int>& numsis the caller's vector, not a copy. Without the&, the function would rotate a copy and the caller would see no change. - Signed index. The size is stored in an
int, son - 1and the loop conditioni > 0behave normally. With an unsigned variable such assize_t i, a loop likefor (i = n - 1; i >= 0; i--)would never end, because an unsigned value can't go below 0. - The standard library has this.
rotate(nums.begin(), nums.end() - 1, nums.end())from<algorithm>performs the same rotation. Writing the loop by hand is the point of this lesson.
Complexity
Time: O(n). The loop runs n - 1 times, and each iteration is one assignment.
Space: O(1). The code uses two integers, n and last, and the loop counter, whatever the size of the vector.
Edge cases and common mistakes
- One element. For
[7], the loop doesn't run andnums[0] = lastwrites the same value back. The vector stays[7]. - Two elements.
[1, 2]becomes[2, 1]. - An empty vector.
nums[n - 1]would benums[-1], which is undefined behaviour. The lesson's tests don't use an empty vector, but code that may receive one should start withif (nums.empty()) return;. - Shifting left to right. Every element ends up equal to the first one, because each assignment copies a value that was just overwritten.
- Forgetting to save the last element. The first assignment, to
nums[n - 1], destroys it, and there is nothing left to put at index 0. - Writing
i >= 0. The loop would then evaluatenums[-1]on its last pass, which is undefined behaviour.
Testing
[1, 2, 3, 4, 5]becomes[5, 1, 2, 3, 4].[4, -2, 13, 1]becomes[1, 4, -2, 13].[7]stays[7].[1, 2]becomes[2, 1].