Problem overview
The method rotate receives an array of integers nums and moves every element one position to the right. The element at the end wraps around to the front. The method returns nothing: it must change nums itself, without building a second array, so the extra memory stays constant.
For nums = [1, 2, 3, 4, 5] the array becomes [5, 1, 2, 3, 4]. For [4, -2, 13, 1] it becomes [1, 4, -2, 13]. The time budget is O(n).
Approach: save the last element, shift, then place it first
After a rotation, each element except the last sits where its left neighbour used to be, and the last element lands at index 0. Only that last element has nowhere to go, since the slot to its right doesn't exist. So the plan has three parts:
- Remember the last element in a variable, because the shifting will overwrite its slot.
- Copy every other element one slot to the right.
- Write the remembered value into slot 0.
The direction of the copying matters. If you copied left to right with nums[i] = nums[i - 1], the first assignment would overwrite nums[1] with nums[0], and the next step would read that already overwritten value, filling the array with copies of the first element. Going right to left avoids it: each iteration reads nums[i - 1], which hasn't been touched yet, and writes into nums[i], whose old value has already been copied onward or saved.
Tracing [1, 2, 3, 4, 5] with last = 5: the loop turns it into [1, 1, 2, 3, 4] one assignment at a time, from the right end, and then writing last into slot 0 gives [5, 1, 2, 3, 4].
Step by step
- Save the length and the last element. Declare
nasnums.lengthandlastasnums[n - 1]. This copy is what lets the slot be overwritten safely. - Loop from the right. Start
iatn - 1and count down whilei > 0. The loop stops before index 0, because slot 0 has no left neighbour to copy from. - Shift one element. Assign
nums[i] = nums[i - 1]. Every element moves one slot to the right. - Wrap the last element. After the loop, assign
nums[0] = last. The old first element was already copied into slot 1 by the final iteration, so slot 0 is free.
The solution in JavaScript
class Solution {
rotate(nums) {
let n = nums.length;
let last = nums[n - 1];
for (let i = n - 1; i > 0; i--) {
nums[i] = nums[i - 1];
}
nums[0] = last;
}
}
The JavaScript details worth a look:
- In-place means no return value. Arrays are passed by reference, so the method changes the caller's array directly. That is why the method has no
returnand the lesson's tests look atnumsafterwards. - A built-in alternative.
nums.unshift(nums.pop())does the same job in one line:pop()removes the last element, andunshiftputs it at the front. It is shorter, butunshiftshifts every element internally, so it is the sameO(n)work, now hidden. The explicit loop shows what is happening. - A decreasing loop.
for (let i = n - 1; i > 0; i--)counts down.letscopesito the loop. - Arrays hold any index. Writing to
nums[0]or readingnums[n - 1]is plain indexing. JavaScript doesn't stop you from reading an index that doesn't exist, it just givesundefined, which matters in the next section.
Complexity
Time: O(n). The loop makes n - 1 assignments, each constant time. The other statements run once.
Space: O(1). The extra memory is the two variables n and last, however long the array is.
Edge cases and common mistakes
- One element. For
[7],lastis 7, the loop doesn't run, andnums[0] = 7changes nothing. The array stays[7]. - Two elements.
[1, 2]becomes[2, 1]. - An empty array. Here the code misbehaves. With
n = 0,nums[-1]isundefined, the loop doesn't run, and the last line assignsundefinedtonums[0], leaving the array as[undefined]. The lesson doesn't test an empty array. If you want it handled, return early whennis 0. - Looping left to right. Every slot would end up holding the first value, as described in the approach.
- Looping down to
i >= 0. That would readnums[-1], which isundefined, and write it into slot 0. - Forgetting to save
lastfirst. Once the shifting overwrites the final slot, the wrapped value is gone. - Returning a new array. A rotated copy leaves the original unchanged, so the in-place requirement fails.
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].