Rotate an Array

The Idea

Rotating right by k means the last k values jump to the front. Reverse the whole array and they are at the front already — backwards, and so is everything else. Now reverse the first k, then reverse the rest, and both blocks read correctly again. Three linear reversals, no copy of the array, and k taken modulo the length so a full turn costs nothing.

Real-World Example

A display board cycles a queue of adverts every few seconds. Instead of copying the whole queue on each tick, the renderer flips it end to end and flips the two blocks back — the same memory, and nothing allocated on a path that runs all day.

The Code

def rotate(nums, k):
    k %= len(nums)

    def reverse(lo, hi):
        while lo < hi:
            nums[lo], nums[hi] = nums[hi], nums[lo]
            lo, hi = lo + 1, hi - 1

    reverse(0, len(nums) - 1)   # flip the whole row
    reverse(0, k - 1)           # put the first block back in order
    reverse(k, len(nums) - 1)   # and the rest
    return nums

print(rotate([1, 2, 3, 4, 5], 2))   # [4, 5, 1, 2, 3]

k %= len(nums)
reverse(0, len(nums) - 1)
reverse(0, k - 1)
reverse(k, ___)