The problem
Rotate a list to the right by k steps, in place.
Input: [1, 2, 3, 4, 5, 6, 7], k = 3 Output: [5, 6, 7, 1, 2, 3, 4]
Picture it
Picture a carousel of seats. Turning it by k is the same as three flips: flip the whole row, then flip the first k seats, then flip the rest.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
reverse(all), reverse(first k), reverse(rest). O(n), O(1).
Python solution
def rotate(a, k):
k %= len(a)
reverse(a, 0, len(a) - 1)
reverse(a, 0, k - 1)
reverse(a, k, len(a) - 1)
def reverse(a, i, j):
while i < j:
a[i], a[j] = a[j], a[i]
i, j = i + 1, j - 1In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.