Problem overview
The function rotate receives a slice of integers, nums, and moves every element one position to the right. The last element wraps around to the front. The slice must be changed in place, with O(1) auxiliary space and O(n) time, and the function returns nothing.
For [1, 2, 3, 4, 5] the slice becomes [5, 1, 2, 3, 4]. For [4, -2, 13, 1] it becomes [1, 4, -2, 13].
Approach: save the last element, shift, then place it
Building a new slice with the last element first would be easy, but the problem forbids a second array. In place, every element has to move one slot to the right, and the last one has nowhere to go, because it would fall off the end. So before shifting, keep a copy of that one element in a variable.
The direction of the shift matters. If you copied from left to right, writing nums[1] = nums[0] would overwrite the old nums[1] before it was used, and every element would end up equal to the first. Going from right to left avoids that: when the loop writes nums[i], the old value there has already been copied to nums[i+1] (or was the saved last element), so nothing is lost. After the loop, slot 0 is free, and the saved value goes there.
On [1, 2, 3, 4, 5]: save 5. Then nums[4] = 4 gives [1, 2, 3, 4, 4], nums[3] = 3 gives [1, 2, 3, 3, 4], then [1, 2, 2, 3, 4] and [1, 1, 2, 3, 4]. Finally nums[0] = 5 gives [5, 1, 2, 3, 4].
Step by step
- Store the length in
nwithn := len(nums). - Save the last element in
lastwithlast := nums[n-1], before any shifting overwrites it. - Loop from
n - 1down to 1 with a loop variablei. The conditioni > 0stops before index 0, because the first slot has no left neighbour to copy from. - Copy each element to the right:
nums[i] = nums[i-1]. Readingnums[i-1]happens before anything overwrites it, which is why the loop runs right to left. - Write the saved element into
nums[0]. The loop's last iteration already copied the old first element to slot 1, so slot 0 is free.
The solution in Go
func rotate(nums []int) {
n := len(nums)
last := nums[n-1]
for i := n - 1; i > 0; i-- {
nums[i] = nums[i-1]
}
nums[0] = last
}
The Go details worth a closer look:
- No return value, yet the caller sees the change. A slice is a small header (pointer, length, capacity) that refers to an array. Passing
numscopies the header, but the copy points at the same array. Writingnums[i] = ...therefore changes the caller's data. Afterrotate(a)witha = []int{1, 2, 3, 4, 5}, the variableaprints[5 1 2 3 4]. - Reassigning
numswould not work. A line likenums = append(...)inside the function would change only the local header, and the caller would see no change. That is why the lesson edits the elements in place. - A counting-down loop. The three-part
forworks with a decreasing variable:i := n - 1; i > 0; i--. The variableiexists only inside the loop. - Short declarations.
nandlastare declared with:=and get the typeintfrom their values. - An empty slice panics. For
[]int{},nis 0 andnums[n-1]isnums[-1], which stops the program with "index out of range [-1]". Go checks every index at run time. The lesson's slices are not empty, but a general-purpose version would start withif n < 2 { return }.
Complexity
Time: O(n). The loop runs n - 1 times with one assignment each.
Space: O(1). The function keeps n, last and the loop variable. No new slice is created.
Edge cases and common mistakes
- One element.
[7]stays[7]:lastis 7, the loop doesn't run, and slot 0 gets 7 again. - Two elements.
[1, 2]becomes[2, 1]. - Empty slice. It panics, as described above.
- Looping left to right.
nums[i] = nums[i-1]in ascending order copies the first element into every slot. - Forgetting to save the last element. The loop overwrites it with
nums[n-2], and the wrap-around value is gone. - Looping down to 0. With
i >= 0, the last iteration readsnums[-1]and panics. - Returning a new slice. The task is to modify the given one; building and returning another violates the space limit.
Testing
[1, 2, 3, 4, 5]becomes[5, 1, 2, 3, 4].[4, -2, 13, 1]becomes[1, 4, -2, 13].[7]stays[7].[1, 2]becomes[2, 1].