Practice: Rotating a Row of Seats

Rotating an array moves its last k elements to the front, and doing it inside the array, without a second one, practises index arithmetic and the cost of moving elements. This card covers it as an exercise, with an answer to check yours against.

A row of six theatre seats holds guests 1 2 3 4 5 6. The usher moves everyone k seats to the right, and guests pushed past the end wrap round to the start, so with k = 2 the row becomes 5 6 1 2 3 4. Using no second array:

1. Say at which index the guest at index i ends up, for any k, including a k larger than the row.
2. Write rotate(seats, k) so that it rearranges the list in place.
3. State its time and its extra space, and compare them with moving everyone one seat to the right, k times over.

def reverse(seats: list[int], left: int, right: int) -> None:
    while left < right:
        seats[left], seats[right] = seats[right], seats[left]
        left += 1
        right -= 1


def rotate(seats: list[int], k: int) -> None:
    n = len(seats)
    if n == 0:
        return
    k = k % n
    reverse(seats, 0, n - 1)
    reverse(seats, 0, k - 1)
    reverse(seats, k, n - 1)


for k in [2, 8, 0]:
    seats = [1, 2, 3, 4, 5, 6]
    rotate(seats, k)
    print(f"k = {k}: {seats}")

k = 2: [5, 6, 1, 2, 3, 4]
k = 8: [5, 6, 1, 2, 3, 4]
k = 0: [1, 2, 3, 4, 5, 6]