Problem overview
The method rotate receives a list nums and moves every element one position to the right. The last element wraps around to the front. The change happens in place: the method returns nothing, and the caller sees the modified list. It must run in O(n) time and use O(1) extra space, so building a second list isn't allowed.
For [1, 2, 3, 4, 5] the result is [5, 1, 2, 3, 4]. Each of 1, 2, 3 and 4 moved one place right, and 5 jumped to the front. For [4, -2, 13, 1] the result is [1, 4, -2, 13].
Approach: save the last, shift the rest, drop it in front
The last element is the only one that has nowhere to go, since there is no slot to its right. So save it in a variable first. Then every other element can move one slot right. Finally the saved value goes into slot 0, which has been freed.
The order of the shifting matters. If you copy nums[0] into nums[1] first, you overwrite nums[1] before it was copied anywhere, and the value is lost. Going from the right end to the left avoids this. When the loop writes into slot i, the old value of that slot has already been copied to slot i + 1 (or, for the last slot, saved in the variable).
Step by step
- Record the length and the last element.
n = len(nums)andlast = nums[-1]. A negative index counts from the end, so-1is the last element. The saved value is a plain number, not a reference into the list, so later writes can't change it. - Loop from
n - 1down to 1.range(n - 1, 0, -1)starts at the last index and counts down by one. The stop value 0 is excluded, so the last value ofiis 1. - Copy each neighbour to the right.
nums[i] = nums[i - 1]. In each pass,nums[i - 1]still holds its original value, because only slots to the right of it have been written. - Put the saved element in front. After the loop,
nums[0] = last. The old first element was already copied into slot 1 by the last pass, so overwriting slot 0 loses nothing.
Tracing [1, 2, 3]: last is 3. With i = 2 the list becomes [1, 2, 2]. With i = 1 it becomes [1, 1, 2]. Finally nums[0] = 3 gives [3, 1, 2].
The solution in Python
class Solution:
def rotate(self, nums: List[int]) -> None:
n = len(nums)
last = nums[-1]
for i in range(n - 1, 0, -1):
nums[i] = nums[i - 1]
nums[0] = last
Python details that matter here:
- In place means changing the object. The assignments
nums[i] = ...modify the list the caller passed in. Writingnums = [last] + nums[:-1]would build a new list and rebind the local namenums, and the caller's list would stay as it was. It would also useO(n)extra space. - The return type is
None. The method has noreturn, so it returnsNoneand the result is read from the list itself. rangewith three arguments isrange(start, stop, step). A negative step counts down, andstopis never reached.- Library shortcut.
nums.insert(0, nums.pop())also rotates in place. It is short, butinsert(0, ...)shifts every element internally, so it does the same work as the loop behind the scenes. The lesson writes the loop to show the shifting.
Complexity
Time: O(n). The loop runs n - 1 times and each pass is one assignment.
Space: O(1). The method uses only n, last and the loop variable, however long the list is.
Edge cases and common mistakes
- One element.
[7]stays[7]. The loop range is empty, andnums[0] = lastwrites the same value back. - Two elements.
[1, 2]becomes[2, 1]. - Empty list.
nums[-1]raisesIndexError, since there is no last element. The lesson's inputs are not empty. - Shifting left to right. A loop like
for i in range(1, n): nums[i] = nums[i - 1]copies the first element everywhere.[1, 2, 3, 4, 5]becomes[1, 1, 1, 1, 1]. - Forgetting to save the last element. It is overwritten by the first pass of the loop, and nothing is left to put in front.
- Stopping the range at 1.
range(n - 1, 1, -1)never writes slot 1, so the old second element stays where it was.
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].