Rotate in place
Three reversals, no extra list. About 10 minutes.
A neat trick with reversing
Rotating right by k moves the last k values to the front. Now watch what reversing the whole array does to 1, 2, 3, 4, 5: it becomes 5, 4, 3, 2, 1. The last two values, 4 and 5, are now at the front, just backwards. And the rest is at the back, also backwards.
So one reversal puts every value in the right half. Each half is just facing the wrong way.
Then turn each part round
Reverse the first k values, then reverse the rest. Each part now faces the right way, and the array is rotated: 4, 5, 1, 2, 3.
You only ever swapped values inside the array, using the reverse you wrote earlier, so no second array was needed. Three reversals, and the job is done.
def reverse(i, j):
while i < j:
nums[i], nums[j] = nums[j], nums[i]
i, j = i + 1, j - 1
k = k % len(nums) if nums else 0
reverse(0, len(nums) - 1)
reverse(0, k - 1)
reverse(k, len(nums) - 1)
return numsReverse everything: [5, 4, 3, 2, 1].
You reverse all of 1, 2, 3, 4, 5, 6, then the first 2 values, then the rest. What do you get?
- A5, 6, 1, 2, 3, 4
- B3, 4, 5, 6, 1, 2
- C6, 5, 4, 3, 2, 1
Show the answer
5, 6, 1, 2, 3, 4. That's the array rotated right by 2: the last two values moved to the front.
Rotate in place
Rotate the list right by k places without building a second list, and return it. k can be larger than the length.
nums = [1, 2, 3, 4, 5], k = 2 → [4, 5, 1, 2, 3]
0 ≤ n ≤ 1,000 · 0 ≤ k ≤ 1,000,000