Problem overview
The method rotate receives an array of numbers, nums, and must rotate it by one position to the right, in place. Every element moves one slot to the right, and the last element wraps around to the front. The method returns nothing (void): the result is the changed nums itself.
For [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 statement asks for O(n) time and O(1) auxiliary space, so building a second array is not allowed.
Approach: save the last element, shift, then place it
If you simply wrote nums[i] = nums[i - 1] for every i, you would run into two problems. The last element would be overwritten before it could wrap to the front, so it has to be saved first. And the order of the copies matters: going left to right, each copy would overwrite the value that the next copy needs, and the first element would spread across the whole array.
Going from right to left avoids this. When the loop writes nums[i], it reads nums[i - 1], which has not been touched yet. By the time the loop finishes, every element from index 1 up holds its left neighbour, and slot 0 is a leftover copy that can be overwritten with the saved last element.
On [1, 2, 3, 4, 5], with last = 5:
- Copy 4 into slot 4:
[1, 2, 3, 4, 4]. - Copy 3 into slot 3:
[1, 2, 3, 3, 4]. - Copy 2 into slot 2:
[1, 2, 2, 3, 4]. - Copy 1 into slot 1:
[1, 1, 2, 3, 4]. - Put the saved 5 into slot 0:
[5, 1, 2, 3, 4].
Step by step
- Save the length and the last element. Declare
nasnums.lengthandlastasnums[n - 1], both typednumber. The copy inlastis the only extra storage. - Loop from
n - 1down to 1. The conditioni > 0stops before 0, because slot 0 has no left neighbour to copy from. - Shift. Inside the loop, assign
nums[i] = nums[i - 1]. - Wrap. After the loop, assign
nums[0] = last.
The solution in TypeScript
class Solution {
rotate(nums: number[]): void {
let n: number = nums.length;
let last: number = nums[n - 1];
for (let i = n - 1; i > 0; i--) {
nums[i] = nums[i - 1];
}
nums[0] = last;
}
}
The TypeScript details worth a closer look:
- Arrays are passed by reference. The method changes the very array the caller passed in, so nothing needs to be returned. That is why the return type is
void. - Annotations are optional here.
let n: number = nums.length;means the same aslet n = nums.length;, because TypeScript infers the type. Annotations are erased when the code compiles to JavaScript, so they cost nothing at run time. - A decreasing loop.
for (let i = n - 1; i > 0; i--)counts down. Each iteration reads a slot that hasn't been overwritten yet.
Complexity
Time: O(n). The loop makes n - 1 assignments.
Space: O(1). Besides the array itself, the method keeps n, last and i.
Edge cases and common mistakes
- One element. For
[7]the loop never runs andnums[0]is set to itself, so the array stays[7]. - An empty array. The array has no last element:
nums[-1]isundefined, and the final assignment putsundefinedinto slot 0, leaving the array as[undefined]. Add a guard such asif (n === 0) return;if empty input is possible. - Looping left to right.
nums[i] = nums[i - 1]in increasing order copies the first element over everything:[1, 2, 3]would become[1, 1, 1]. - Forgetting to save
last. The last value is overwritten by the first iteration and can't be recovered. - Running the loop down to 0. Then
nums[0] = nums[-1]would readundefinedand ruin the front slot.
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].