Problem overview
rotate(nums []int, k int) rotates the slice nums to the right by k places, in place. One rotation moves every number one position to the right and brings the last number to the front. The function returns nothing: it changes the slice it receives. The lesson asks for O(n) time and O(1) extra memory, and guarantees 1 <= k <= len(nums).
With nums = [1, 2, 3, 4, 5] and k = 2, the first rotation gives [5, 1, 2, 3, 4] and the second gives [4, 5, 1, 2, 3]. With [1, 2, 3, 4, 5, 6, 7, 8] and k = 3 the result is [6, 7, 8, 1, 2, 3, 4, 5].
Approach: send every element straight to its final slot
Rotating one step at a time, k times, costs O(n * k). Copying into a second slice at the right offsets is O(n) time but needs O(n) extra space. To get both bounds, move each element directly to where it ends up, using a few variables as the only extra memory.
After k right rotations, the element at position i sits at position (i + k) % n. The modulo wraps positions past the end back to the front. Moving one element there would overwrite another, so that one must move on in turn: it goes to its own destination, and so on. The positions form a chain that eventually returns to the start, which is a cycle. With n = 5 and k = 2, the chain is 0, 2, 4, 1, 3 and back to 0, a single cycle. With n = 6 and k = 2 there are two cycles, 0, 2, 4 and 1, 3, 5. Cycles never share positions, so once one is finished, the next begins at the following position.
The solution carries the displaced value in the slot at startIndex instead of in a separate variable. Each step swaps the carried value with the element at its destination. The carried value lands in its final position, and the displaced element becomes the new carried value, ready to be placed next. Every step finishes one element for good.
Step by step
- Declare three variables on one line with
n, index, startIndex := len(nums), 0, 0.nis the length,indexis the position whose element is being placed, andstartIndexis where the current cycle began. - Loop exactly
ntimes. Each pass settles one element, sonpasses settle them all, however many cycles there are. - Compute the destination as
nextIndex := (index + k) % n. - Swap
nums[nextIndex]withnums[startIndex]. The carried value goes to its destination, and the element that was there is picked up in its place. - Move on:
index = nextIndex. The picked-up element belongs at the destination of this new position. - Detect the end of a cycle. When
index == startIndex, the chain has come back to its beginning, and the value waiting atstartIndexis already the right one. Set bothstartIndexandindextoindex + 1to start the next cycle.
The solution in Go
func rotate(nums []int, k int) {
n, index, startIndex := len(nums), 0, 0
for i := 0; i < n; i++ {
nextIndex := (index + k) % n
nums[nextIndex], nums[startIndex] = nums[startIndex], nums[nextIndex]
index = nextIndex
if index == startIndex {
startIndex, index = index+1, index+1
}
}
}
Here is the run for nums = [1, 2, 3, 4, 5], k = 2, showing the slice after each pass:
| Pass | Swap | Slice after the swap | index |
|---|---|---|---|
| 0 | positions 2 and 0 | [3, 2, 1, 4, 5] | 2 |
| 1 | positions 4 and 0 | [5, 2, 1, 4, 3] | 4 |
| 2 | positions 1 and 0 | [2, 5, 1, 4, 3] | 1 |
| 3 | positions 3 and 0 | [4, 5, 1, 2, 3] | 3 |
| 4 | positions 0 and 0 | [4, 5, 1, 2, 3] | 0, then reset to 1 |
The last pass swaps the position with itself, which changes nothing: the carried value, 4, has just come back to where it belongs. The slice is now [4, 5, 1, 2, 3].
The Go details worth a closer look:
- Swapping without a temporary. The tuple assignment
a, b = b, aevaluates the right-hand side first and then assigns, so it swaps two slice elements in one line. - The slice is changed in place. A slice value is a small header pointing to a backing array. The function receives a copy of the header, but it points to the same array, so writing
nums[i]changes what the caller sees. Reassigningnumsitself, or callingappend, would not. - Multiple assignment at the end of a cycle.
startIndex, index = index+1, index+1sets both variables to the same new value in a single statement. - The modulo is safe.
%in Go takes the sign of the dividend, butindex + kis never negative here, so the result is always between 0 andn - 1. :=declares several variables at once. All three ofn,indexandstartIndexareint, because the right-hand values are integers.
Complexity
Time: O(n). The loop runs exactly n times, and each pass does a constant amount of work: one modulo, one swap, a comparison.
Space: O(1). The function uses three integers and a loop counter. The slice itself is rearranged in place.
Edge cases and common mistakes
- One element. With
n = 1the loop runs once, swaps position 0 with itself and finishes. The slice is unchanged. kequal ton. Every destination is the position itself, so all the swaps are no-ops and the slice is unchanged, which is the correct result of a full turn. The cycles here all have length 1.- Several cycles. When
nandkshare a divisor, one chain doesn't visit every position.[1, 2, 3, 4, 5, 6]withk = 2becomes[5, 6, 1, 2, 3, 4]only because the reset toindex + 1starts a second cycle. Without that reset, positions 1, 3 and 5 would stay behind. - Looping until
indexreturns to 0. That stops after the first cycle. Counting passes tonis what covers all the cycles. - Dropping the
% n. Without the modulo,index + kcan reach past the end of the slice, and indexing there panics. The modulo is what wraps the destination back to the front. - Returning a new slice. The function must change
numsitself. Building a rotated copy and assigning it tonumswould leave the caller's slice as it was.
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 = [1, 2, 3, 4],k = 4gives[1, 2, 3, 4].nums = [7],k = 1gives[7].
