Shift a playlist k places to the right, in place

Reduce k modulo the length, then reverse the whole list, reverse the first k songs and reverse the rest. Three in-place reversals give the shifted order with O(n) time and O(1) extra space. Slicing (songs[-k:] + songs[:-k]) is shorter but builds a new list.

Reversing everything puts the last k songs at the front, but backwards; the two smaller reversals fix the order inside each part.

k % n handles k larger than the list and k equal to it (no change). Guard n = 0 first.

A cycle-following method also works in O(1) space but is easier to get wrong under pressure.

def shift_right(songs: list[int], k: int) -> list[int]:
    n = len(songs)
    if n == 0:
        return songs
    k %= n

    def flip(lo: int, hi: int) -> None:
        while lo < hi:
            songs[lo], songs[hi] = songs[hi], songs[lo]
            lo, hi = lo + 1, hi - 1

    flip(0, n - 1)
    flip(0, k - 1)
    flip(k, n - 1)
    return songs

Common mistakes

• Skipping k %= n, which indexes past the end when k > n.
• Assigning songs = songs[-k:] + songs[:-k] inside a function, which rebinds a local name and leaves the caller's list unchanged.

Mention the slicing one-liner and why the in-place version is asked: memory, and mutating the caller's list.

Follow-up questions

Think of your answer first, then open the hint.

1. How would you shift left instead?

   Show hint

   Shift right by n - k, or reverse the first k, the rest, then the whole list.

2. What about a linked list?

   Show hint

   Find the new tail at n - k - 1, cut there and join the old tail to the old head.