Problem overview
The method rotate receives a list nums and a number k. One rotation to the right moves every element one place to the right, and the last element moves to the front. The method applies k rotations and changes nums in place. It returns nothing. It must run in O(n) time with O(1) extra space, so building a rotated copy is not allowed. The constraints guarantee 1 <= k <= len(nums).
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 answer. For [1, 2, 3, 4, 5, 6, 7, 8] and k = 3 the answer is [6, 7, 8, 1, 2, 3, 4, 5].
Approach: move every element straight to its final slot
Rotating one step at a time k times costs O(n * k). A copy into a new list is O(n) but uses O(n) space. To meet both limits, each element has to go directly to its final position without a spare list.
That final position is easy to compute. After k rotations, the element at index i ends up at index (i + k) % n, where n is the length of the list. The modulo wraps indexes past the end back to the front. In [1, 2, 3, 4, 5] with k = 2, the element 4 at index 3 goes to (3 + 2) % 5 = 0.
The problem is that the destination slot is occupied. The fix is to carry a value along. Start at index 0. The value there goes to its destination, and the value that was in the destination is picked up and now has to move to its own destination, and so on. Following the chain 0, k, 2k, ... (all mod n) visits positions until it returns to the start. That loop is a cycle.
One cycle does not always cover the whole list. When n = 6 and k = 2, the chain from 0 visits only 0, 2 and 4. Indexes 1, 3 and 5 form a second cycle. In general the number of cycles is the greatest common divisor of n and k. When a cycle closes, the code moves on to the next start index.
A trace
For nums = [1, 2, 3, 4, 5, 6] and k = 2, the list after each of the six swaps looks like this, with the values of index and startIndex after the swap and before any restart:
[3, 2, 1, 4, 5, 6] index=2 startIndex=0
[5, 2, 1, 4, 3, 6] index=4 startIndex=0
[5, 2, 1, 4, 3, 6] index=0 startIndex=0 (cycle closed, start moves to 1)
[5, 4, 1, 2, 3, 6] index=3 startIndex=1
[5, 6, 1, 2, 3, 4] index=5 startIndex=1
[5, 6, 1, 2, 3, 4] index=1 startIndex=1 (cycle closed)
The final list is [5, 6, 1, 2, 3, 4], which is the original rotated right by 2.
Step by step
- Set up the variables on one line.
nis the length,indexis the slot the cycle is currently at, andstartIndexis where the current cycle began. Both pointers start at 0. - Loop exactly
ntimes. Every element is moved into its final place exactly once, sonswaps are enough, across all cycles together. The loop variable_is a name for a value that isn't used. - Compute the destination.
nextIndex = (index + k) % nis where the element currently atindexbelongs. - Swap with the start slot. The slot at
startIndexacts as the carrying hand. Swapping it withnums[nextIndex]puts the carried value into its destination and picks up the old occupant, which is the next value to place. - Advance the pointer.
index = nextIndexmoves to the slot whose value was just picked up. - Detect a closed cycle. When
indexreturns tostartIndex, the cycle is complete, and both pointers move to the next index so a new cycle can begin.
The solution in Python
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n, index, startIndex = len(nums), 0, 0
for _ in range(n):
nextIndex = (index + k) % n
nums[nextIndex], nums[startIndex] = nums[startIndex], nums[nextIndex]
index = nextIndex
if index == startIndex:
startIndex, index = index + 1, index + 1
Python details worth knowing:
- Tuple swap.
a, b = b, aevaluates the right side first and then assigns, so no temporary variable is needed. The same pattern appears in the restart line, where both pointers get the oldindex + 1. - In-place means mutating the list. The method changes the list the caller passed. Writing
nums = nums[-k:] + nums[:-k]would only rebind the local name and leave the caller's list unchanged. The method returnsNone, as the-> Noneannotation says. %with positive numbers. Hereindex + kis never negative, so%simply wraps around. (For negative numbers Python's%result takes the sign of the divisor, so-1 % 5is 4.)- The restart can go one past the end. After the last swap
startIndexcan becomen, but the loop has finished by then, so it is never used as an index.
Complexity
Time: O(n). The loop runs exactly n times, and each iteration does constant work: one modulo, one swap and a comparison.
Space: O(1). The method keeps a few integers and swaps elements within the list.
Edge cases and common mistakes
kequal to the length. The destination of every index is the index itself, since(index + n) % n == index. Each swap exchanges a slot with itself, the cycle closes at once, and the list stays unchanged, which is correct, becausenrotations restore the original order.- A single element. With
n = 1andk = 1, the one iteration swaps the slot with itself. nandkshare a factor. This is the case with several cycles. Following only the cycle from index 0 would leave the other elements in place. Forn = 6andk = 2it would rotate only indexes 0, 2 and 4. The restart step handles this.- Looping until the pointers meet instead of
ntimes. The count ofnswaps is what ends the algorithm, and the cycle check only decides where the next cycle starts. - Rotating left by mistake. Using
(index - k) % nwould shift elements the other way.
Testing
nums = [1, 2, 3, 4, 5],k = 2becomes[4, 5, 1, 2, 3].nums = [1, 2, 3, 4, 5, 6],k = 2becomes[5, 6, 1, 2, 3, 4].nums = [1, 2, 3, 4, 5, 6],k = 3becomes[4, 5, 6, 1, 2, 3].nums = [1, 2, 3, 4, 5],k = 5stays[1, 2, 3, 4, 5].
