Rotate Right By K
Problem
Shift every element of a list k positions to the right, so values pushed off the end reappear at the front. The rearrangement must happen inside the same list rather than in a freshly allocated one. The shift amount k is zero or positive and may be larger than the list itself.
Examples
Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 3
Output: [5, 6, 7, 1, 2, 3, 4]
Why: the last three values wrap around to the frontInput: nums = [1, 2], k = 5
Output: [2, 1]
Why: five shifts over two slots is the same as one shiftInput: nums = [], k = 3
Output: []
Why: edge case, an empty list has nothing to wrapHints
0 / 3
Shifting one position at a time k times is correct but wasteful, and k can be much larger than the list. Start by reducing k to something that fits.
Look at where each block ends up rather than each element: the tail block and the head block simply swap places while each keeps its internal order.
Turn the whole list back to front in place. The two blocks are now on the correct sides but each reads backwards, so turn the first k elements back to front and then the remaining elements back to front.
Solution
A rotation swaps two blocks: the last k elements move ahead of the first n-k. Reversing the entire list puts both blocks on the right side but internally backwards, so reversing each block separately restores its order. Reducing k modulo the length first makes over-large shifts free, and the early return covers the empty list. Time is O(n) across three reversals, and space is O(1).
def rotate_right(nums, k):
n = len(nums)
if n == 0:
return nums
k %= n # a whole turn changes nothing
def flip(i, j): # reverse the stretch nums[i..j] in place
while i < j:
nums[i], nums[j] = nums[j], nums[i]
i, j = i + 1, j - 1
flip(0, n - 1) # both blocks land on the correct side
flip(0, k - 1) # repair the block now at the front
flip(k, n - 1) # repair the block now at the back
return nums
print(rotate_right([1, 2, 3, 4, 5, 6, 7], 3)) # -> [5, 6, 7, 1, 2, 3, 4]
print(rotate_right([1, 2], 5)) # -> [2, 1]
print(rotate_right([], 3)) # -> []Stuck on the idea rather than the code? Rotate an Array covers it.