Problem overview
The method rotate receives an array nums and a number k. It must rotate the array k times to the right, in place. One rotation moves every element one position to the right, and the last element wraps around to the front. The method returns nothing: the caller's array itself must end up rotated, using O(1) extra memory and O(n) time.
For nums = [1, 2, 3, 4, 5] and k = 2 the result is [4, 5, 1, 2, 3]. After one rotation the array is [5, 1, 2, 3, 4], and after the second it is [4, 5, 1, 2, 3].
Approach: move each element straight to its final slot
Doing k single rotations costs O(n) each, so O(n × k) in total. Copying into a second array is simple but breaks the memory limit. The faster idea is to compute where every element ends up: after k rotations, the element at index i sits at index (i + k) % n. The modulo handles the wrap-around past the end.
Copying an element to its target would overwrite the element already there, which also needs to move. So you carry it along: pick up the displaced element and drop it in its own target, and so on. Following the chain of targets from some index, you visit i, (i + k) % n, (i + 2k) % n, and so on, until you return to i. That chain is a cycle.
One cycle doesn't always cover the whole array. When n and k share a common divisor, the indexes split into several separate cycles. With n = 6 and k = 2, one cycle visits indexes 0, 2, 4 and another visits 1, 3, 5. Each cycle needs its own starting point, and that is why the code has a startIndex.
The code keeps the carried element in slot startIndex. Each step swaps it into its target slot, which hands back that slot's old element as the new carried element. When the walk comes back to startIndex, the swap is between a slot and itself, which changes nothing: the carried element is already at home, the cycle is closed, and the next cycle starts at startIndex + 1.
The trace for [1, 2, 3, 4, 5] with k = 2 shows it. Each line is the array after one swap:
swap 0: nextIndex 2 -> [3, 2, 1, 4, 5]
swap 1: nextIndex 4 -> [5, 2, 1, 4, 3]
swap 2: nextIndex 1 -> [2, 5, 1, 4, 3]
swap 3: nextIndex 3 -> [4, 5, 1, 2, 3]
swap 4: nextIndex 0 -> [4, 5, 1, 2, 3] (back at the start: cycle closed)Step by step
- Declare the three variables on one line:
nfor the length,indexfor the current position in the cycle, andstartIndexfor where the current cycle began. Both positions start at 0. - Loop exactly
ntimes. Every swap puts one element into its final slot, and the cycle-closing step counts too, sonsteps handle allnelements, however many cycles there are. - Compute
nextIndexas(index + k) % n, the target slot of the element currently being carried. - Swap
nums[nextIndex]andnums[startIndex]with array destructuring. The carried element goes to its target, and the target's old element becomes the carried one. - Move
indextonextIndex, because the carried element now belongs atnextIndex + k. - Detect a closed cycle with
index === startIndex. If it is closed, add 1 to both variables to begin the next cycle at the next slot.
The solution in TypeScript
class Solution {
rotate(nums: number[], k: number): void {
let n: number = nums.length, index: number = 0, startIndex: number = 0;
for (let i: number = 0; i < n; i++) {
let nextIndex: number = (index + k) % n;
[nums[nextIndex], nums[startIndex]] = [nums[startIndex], nums[nextIndex]];
index = nextIndex;
if (index === startIndex) {
startIndex++; index++;
}
}
}
}
The TypeScript details worth a closer look:
- Destructuring swap.
[a, b] = [b, a]builds a temporary two-element array on the right, then assigns its elements to the targets on the left. It swaps without a temporary variable. The right side is evaluated completely before any assignment, so no value is lost. - The semicolon before
[. A line that begins with[can be read as a continuation of the line above, as an index into it. The line before the swap ends with a semicolon, and it has to. - In place means mutating the parameter. The method changes the array the caller passed in and returns
void. Writingnums = somethingwould only rebind the local name, and the caller's array would stay unchanged. - The annotations are optional.
let n: number = nums.lengthcan be written aslet n = nums.length, and TypeScript infersnumber. They are erased when compiling to JavaScript either way. - Numbers as indexes. The values are doubles, but
(index + k) % non whole numbers gives a whole number, so it is a valid index. Division would needMath.floor, but this code needs none.
Complexity
Time: O(n). The loop runs exactly n times and each iteration does a constant amount of work: one addition, one modulo, one swap and one comparison.
Space: O(1). The method uses a few numbers. The temporary pair in the swap holds two elements and is discarded at once, so it doesn't grow with n.
Edge cases and common mistakes
- A single element. For
[7]andk = 1the only swap is of a slot with itself, and the array stays[7]. kequal ton. A full turn changes nothing. EverynextIndexequalsindex, every step closes a cycle of length 1, and the array comes out unchanged.- Several cycles.
[1, 2, 3, 4, 5, 6]withk = 2has two cycles. A version withoutstartIndexwould walk the first cycle,0, 2, 4, and leave the odd indexes alone. The correct result is[5, 6, 1, 2, 3, 4]. - Rotating left by mistake. Using
(index - k) % nwould rotate the other way, and in JavaScript the remainder of a negative number is negative, so it could even produce a negative index. - Forgetting the modulo.
index + kcan passn - 1, and writing to such an index silently grows the array instead of failing. - Looping until
index === startIndexonce. That finishes one cycle only. The fixed count ofniterations is what covers every cycle.
Testing
nums = [1, 2, 3, 4, 5],k = 2gives[4, 5, 1, 2, 3].nums = [1, 2, 3, 4, 5, 6, 7, 8],k = 3gives[6, 7, 8, 1, 2, 3, 4, 5].nums = [1, 2, 3, 4, 5, 6],k = 2gives[5, 6, 1, 2, 3, 4].nums = [7],k = 1gives[7].
