LeetCode 189 · Two pointers

Rotate Array, explained with a picture

Turning a carousel with three flips.

Two pointers
▶ Watch it step by step

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 - 1

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.