Problem overview
The method rotate(nums, k) receives an array of numbers and a number k, and rotates the array to the right by k places. One rotation moves every number one position to the right, and the last number moves to the front. The method changes nums in place and returns nothing.
For nums = [1, 2, 3, 4, 5] and k = 2, one rotation gives [5, 1, 2, 3, 4] and a second gives [4, 5, 1, 2, 3], which is the final array. For nums = [1, 2, 3, 4, 5, 6, 7, 8] and k = 3 the result is [6, 7, 8, 1, 2, 3, 4, 5]. The array has between 1 and 30,000 numbers, and k is between 1 and the array's length.
The lesson asks for O(n) time and O(1) extra space, where n is the length of the array.
Approach: move each number straight to its final slot
A rotation by k sends the number at index i to index (i + k) % n. The remainder operator % wraps the index around when it passes the end of the array. In the first example, the number at index 3 goes to (3 + 2) % 5 = 0.
The easy ways to use that rule each cost something. Rotating one step at a time, k times, takes O(n × k) time. Copying into a second array of the same size takes O(n) time but O(n) extra space. The lesson wants both limits at once.
The trick is to follow the movement as a chain. Start at index 0 and take its number out. It belongs at index k, so put it there, which pushes out the number that was there. That number belongs at index 2k, and so on. Each step carries one number to its final place, until the chain comes back to where it began.
The code never keeps the carried number in a separate variable. It keeps it in the slot at startIndex, and each step swaps the carried number with the one in its destination. The swap puts the carried number in its final place, and the number that was there becomes the new carried number, waiting in the start slot.
Here is [1, 2, 3, 4, 5] with k = 2. Each row is one pass of the loop:
pass swap slots array after
1 2 and 0 [3, 2, 1, 4, 5]
2 4 and 0 [5, 2, 1, 4, 3]
3 1 and 0 [2, 5, 1, 4, 3]
4 3 and 0 [4, 5, 1, 2, 3]
5 0 and 0 [4, 5, 1, 2, 3]
After every pass, one more number sits in its final place. In the last pass the carried number's destination is the start slot itself, so the swap does nothing and the chain is closed.
One chain doesn't always cover the whole array. For [1, 2, 3, 4, 5, 6] with k = 2, the chain from index 0 visits only indexes 0, 2 and 4 and then returns to 0. The odd indexes form a second, separate chain. When a chain closes, the code moves the start to the next index and begins a new one.
Step by step
- Record the length and set two positions.
nisnums.length, aconst.indexis where the current chain stands, andstartIndexis where it began and where the carried number waits. Both start at 0. - Loop exactly
ntimes. Each pass finalises one number, sonpasses finish all of them, however many chains there are. The loop variableconly counts passes. - Compute the destination.
nextIndexis(index + k) % n, the place the number atindexmust go. The remainder takes care of the wrap-around. - Swap
nums[nextIndex]withnums[startIndex]. The carried number lands in its final slot, and the previous occupant becomes the new carried number. - Move
indextonextIndex. The chain now stands at the slot just filled, and the next number to place is the one that was displaced there. - Check whether the chain closed. When
index === startIndex, the chain has come back to its beginning. ThenstartIndexandindexboth move forward by one, so the next pass begins a fresh chain at the next position. This is how arrays where the length andkshare a common factor get covered: they split into several chains, and each one needs its own start.
The solution in JavaScript
class Solution {
rotate(nums, k) {
const n = nums.length;
let index = 0, startIndex = 0;
for (let c = 0; c < n; c++) {
const nextIndex = (index + k) % n;
[nums[nextIndex], nums[startIndex]] = [nums[startIndex], nums[nextIndex]];
index = nextIndex;
if (index === startIndex) {
startIndex++; index++;
}
}
}
}
Some JavaScript details worth a closer look:
- Swapping with destructuring.
[a, b] = [b, a]builds an array of the two current values on the right, then assigns them to the targets on the left. It swaps without a temporary variable. It works on array elements too, as innums[nextIndex]. - The semicolon before the bracket. The swap line starts with
[. A missing semicolon on the line above it would make JavaScript read the two lines as one expression. In this code the line before ends with a semicolon. - In-place means no return value. The method changes the array it received, so the caller sees the rotated array in its own variable. A method that builds a new array and returns it would leave
numsunchanged. - A
constcan still be used for the array's contents. The method never reassignsnums; it changes its elements, and that is allowed. - The remainder keeps indexes valid. For non-negative numbers,
(index + k) % nis always between 0 andn - 1. It also works ifkwere larger thann, since the remainder wraps the extra turns.
Complexity
Time: O(n). The loop runs exactly n times, and each pass does a constant amount of work: one remainder, one swap and a comparison. The chains need no extra passes, because the loop count is fixed by the array's length, not by the number of chains.
Space: O(1). Only n, index, startIndex, c and nextIndex are kept. The array is rearranged by swaps, so no second array exists. The swap's temporary two-element array is created and discarded at each pass and has constant size.
Edge cases and common mistakes
- One element. With
nums = [7]andk = 1,nextIndexis 0, the swap changes nothing and the loop ends after one pass. kequal to the length. A full turn leaves the array unchanged. Withnums = [1, 2, 3, 4, 5]andk = 5,(index + k) % nisindexitself, so each pass swaps a slot with itself and moves on to the next one. The array comes out as it went in.- Several chains. With
n = 6andk = 2, the first chain covers three slots and the second covers the other three. Forgetting to restart the chain, as the last step does, leaves half of the array unrotated. The array[1, 2, 3, 4, 5, 6]becomes[5, 6, 1, 2, 3, 4]. - Stopping when
indexreturns to 0. That would be right only when one chain covers everything. Countingnpasses works for every case. - Rotating the wrong way. Using
(index - k) % nwould rotate left, and in JavaScript the remainder of a negative number is negative, which gives an invalid index. Rotating right addsk. - Returning a new array. A solution that builds
nums.slice(-k).concat(nums.slice(0, -k))returns the right values, but it doesn't changenums, and it usesO(n)extra space.
Testing
nums = [1, 2, 3, 4, 5],k = 2becomes[4, 5, 1, 2, 3].nums = [1, 2, 3, 4, 5, 6, 7, 8],k = 3becomes[6, 7, 8, 1, 2, 3, 4, 5].nums = [1, 2, 3, 4, 5, 6],k = 2becomes[5, 6, 1, 2, 3, 4].nums = [1, 2, 3, 4, 5],k = 5stays[1, 2, 3, 4, 5].nums = [7],k = 1stays[7].
