Problem overview
The function rotate receives nums: &mut Vec<i32> and rotates it one position to the right, in place. Every element moves one slot to the right and the last element wraps around to the front. It returns nothing; the caller sees the change in its own vector. For [1, 2, 3, 4, 5] the vector becomes [5, 1, 2, 3, 4], and [4, -2, 13, 1] becomes [1, 4, -2, 13].
The statement asks for O(n) time and O(1) auxiliary space, so building a second vector is not allowed.
Approach: save the last element, shift, then place it
Each element except the last moves to the next index, and the last one ends up at index 0. Shifting everything right would overwrite the last element, so it is saved first in a variable.
The order of the shifts matters. Copying left to right, with nums[i] = nums[i - 1] for increasing i, would copy the first value into every slot, because each assignment reads a slot that the previous step has just overwritten. Going right to left reads every slot before it is overwritten. Slot 4 gets the value of slot 3, then slot 3 gets slot 2, and so on.
On [1, 2, 3, 4, 5], with 5 saved, the vector goes through [1, 2, 3, 4, 4], [1, 2, 3, 3, 4], [1, 2, 2, 3, 4] and [1, 1, 2, 3, 4]. The last step puts the saved 5 at index 0 and gives [5, 1, 2, 3, 4].
Step by step
- Save the end. Declare
nasnums.len()andlastasnums[n - 1]. This copies the number out, so it stays safe while the slots are overwritten. - Shift right to left. Loop with
for i in (1..n).rev(). The range1..nexcludesn, and.rev()walks it backwards, fromn - 1down to 1. - Copy one slot over. Inside the loop,
nums[i] = nums[i - 1];. Each element ends up one slot further right. - Place the saved element. After the loop,
nums[0] = last;. The loop's last iteration has already copied the old first element to index 1, so index 0 is free.
The solution in Rust
impl Solution {
fn rotate(nums: &mut Vec<i32>) {
let n = nums.len();
let last = nums[n - 1];
for i in (1..n).rev() {
nums[i] = nums[i - 1];
}
nums[0] = last;
}
}
Rust details worth knowing:
- The parentheses in
(1..n).rev()are required. Written as1..n.rev(), the method call binds tononly, and the compiler rejects it because an integer has norevmethod. &mut Vec<i32>. The function borrows the caller's vector mutably, so assignments such asnums[i] = ...change the caller's data. There is no return value, and the function can't keep the vector after it returns.- Reading and writing in one statement.
nums[i] = nums[i - 1]compiles because ani32isCopy: the right side is read out as a plain number before the assignment happens. - Library alternative. The standard library has
nums.rotate_right(1), which does the same job. The loop is what that call does, written out.
Complexity
Time: O(n). The loop runs n - 1 times with constant work each.
Space: O(1). The only extra values are n, last and the loop variable.
Edge cases and common mistakes
- One element.
[7]stays[7]. The range1..1is empty, and the last step writes the element onto itself. - Two elements.
[1, 2]becomes[2, 1]. - Empty vector.
nums[n - 1]fails. In an optimized build, 0 minus 1 wraps to the largestusize, and the index panics with "index out of bounds: the len is 0". In a debug build the subtraction itself panics. A guard that returns early when the vector is empty fixes it. - Looping left to right.
for i in 1..n { nums[i] = nums[i - 1]; }turns[1, 2, 3, 4, 5]into[1, 1, 1, 1, 1]. Always read before you overwrite. - Forgetting to save the last element. It is the one value the loop never copies anywhere, so it would be lost.
Testing
[1, 2, 3, 4, 5]becomes[5, 1, 2, 3, 4].[4, -2, 13, 1]becomes[1, 4, -2, 13].[1, 2]becomes[2, 1].[7]stays[7].
