Rotation by reversal in Python lists

Why this matters

A common interview question asks you to move the last few items of a list to the front, without creating a new list. A music player does this when it wraps a playlist around. A card game does this when it deals from the top of a deck that has been cut. The naive way is to shift every item one place, and to repeat that k times. For a long list and a large k, that is slow.

This lesson shows a faster method that uses only the list you already have. You reverse three pieces of the list, one after another. The result is a rotation. The method takes about one pass over the data and needs only a few extra variables. It is a good example of a pattern that appears often in list problems: change a list in place, using the positions of its items as the guide.

This lesson assumes you can write a loop over a list and know that indexes start at 0. The helper for swapping two items is shown in full, so you do not need to have seen it before. Other techniques, such as the sliding window and the difference array, come in other lessons in this module.

The idea in plain words

A rotation moves items along a line and lets the ones at the end wrap around to the front. Take the list [1, 2, 3, 4, 5]. Rotating it to the right by 2 means every item moves 2 places to the right. The last two items, 4 and 5, wrap around and land at the front:

start:           1  2  3  4  5
right by 2:      4  5  1  2  3

Rotating to the left by 2 works the other way. The first two items wrap around to the end:

start:           1  2  3  4  5
left by 2:       3  4  5  1  2

A left rotation by 2 gives the same result as a right rotation by 3, because moving 2 places left is the same as moving 3 places right in a row of 5. Most problems use one direction, so this lesson builds a right rotation first and then shows the left version.

The number k is the number of steps. For a list of length n, a step count of n does nothing, because every item returns to its place. So a step count of 7 on a list of length 5 is the same as a step count of 2. We use the remainder k % n to get the smaller number. You will see this in the code below.

The trick: reverse three parts

Reversing a list means swapping the first item with the last, the second with the second last, and so on, until you reach the middle. Reversing is easy to do in place, and it keeps the same items with the same neighbours, just in the opposite order.

Here is the key fact. To rotate a list to the right by k, do three reversals:

1. Reverse the whole list.
2. Reverse the first k items.
3. Reverse the rest, which is the items from position k to the end.

Look at the example [1, 2, 3, 4, 5, 6, 7] with k equal to 3. Each row shows the list after one step.

start:                     1  2  3  4  5  6  7
1. reverse all:            7  6  5  4  3  2  1
2. reverse first 3:        5  6  7  4  3  2  1
3. reverse the rest:       5  6  7  1  2  3  4

The result [5, 6, 7, 1, 2, 3, 4] is the right rotation by 3. The last three items moved to the front, and the others kept their order.

Here is the reason this works. After step 1, the three items that must go to the front, 5, 6 and 7, sit at the front already, but in the wrong order: 7, 6, 5. Step 2 fixes their order by reversing those first three positions. The other items, 1 to 4, are now at the end in the order 4, 3, 2, 1. Step 3 fixes their order by reversing those four positions. Each item gets reversed twice in total, once in the big reversal and once in a small one, which brings it back to the right order. The two small reversals add up to the fix.

It helps to name the pieces. Call the last k items the tail. In the example, the tail is [5, 6, 7], and the head is the other four items, [1, 2, 3, 4]. A right rotation swaps the tail and the head. Reversing the whole list puts both pieces in reverse order, with the tail first. Reversing each piece on its own puts both back in the correct order.

Writing the reverse helper

You need one helper to reverse a part of a list. It takes the list, the position of the left end, and the position of the right end. Both ends are included. The helper swaps the two ends and moves inward until the ends meet.

Output:

[5, 4, 3, 2, 1]

The loop stops when left is no longer less than right. For a list of length 5, the first swap is between positions 0 and 4, then 1 and 3, and then the two ends meet at position 2. The middle item stays where it is.

The line a[left], a[right] = a[right], a[left] swaps the two items in one step. Python builds both values first and then assigns them, so no temporary variable is needed. In most other languages, the swap needs a third variable called temp, so that the first value is not lost before it is saved.

Reverse with inclusive ends is the convention in this lesson. If you pass left as 2 and right as 2, the loop does not run, and the list is unchanged. That is correct, because a single item reversed is still the same item.

The rotation method

Now combine the three reversals into a function. The function takes the list and the step count k. It returns nothing, because it changes the list directly.

Output:

Start:   [1, 2, 3, 4, 5, 6, 7]
Right by 3: [5, 6, 7, 1, 2, 3, 4]
Right by 10: [5, 6, 7, 1, 2, 3, 4]
Right by 1: [40, 10, 20, 30]

Read the function line by line. The first two lines of the body set up the length and handle the empty list. An empty list has nothing to rotate, and without the check, k % n would divide by zero. The line k = k % n turns a large step count into a small one. In the second call, the step count is 10 and the length is 7, so 10 % 7 is 3, and the output matches the first call.

The three reverse calls are the three steps from the earlier section. The middle call reverses positions 0 to k - 1, which is the tail, now at the front. When k is 0, that call has right equal to -1, and the loop does not run, so the result is the list unchanged. The last call reverses positions k to n - 1, which is the rest of the list.

The print calls separate values with a space, so the output has one space after each label. The first label has two spaces in the source only to line up the text.

Second example: a larger step count and a single item

Take the list [1, 2, 3, 4, 5, 6, 7] again, and rotate it by 10. The remainder is 3, so the code does exactly the same work as the first call. Think about what the output should be before you run it. Ten steps to the right is the same as three steps to the right on a length of seven, so the answer must match the first call. The program confirms it.

Now take a list with one item, [42], and rotate it by 5. The remainder 5 % 1 is 0. The reversal of position 0 to 0 does nothing, and so does the reversal of the empty range. The list stays [42]. This is correct, because one item looks the same after any number of rotations.

Now look at a case where the list is long and k is much larger than the length. A list of length 1000 rotated by 1,000,001 steps has the remainder 1,000,001 % 1000, which is 1. So the work is the same as a rotation by 1. The reversal method costs the same whether k is small or large, because the remainder keeps k below n.

Third example: rotate left

A left rotation by k moves the first k items to the end. The trick is the same, but the three reversals are in a different order:

1. Reverse the first k items.
2. Reverse the rest.
3. Reverse the whole list.

Try it on [1, 2, 3, 4, 5, 6, 7] with k equal to 2. The head is [1, 2] and the rest is [3, 4, 5, 6, 7].

start:                     1  2  3  4  5  6  7
1. reverse first 2:        2  1  3  4  5  6  7
2. reverse the rest:       2  1  7  6  5  4  3
3. reverse all:            3  4  5  6  7  1  2

The result [3, 4, 5, 6, 7, 1, 2] is the left rotation by 2.

Python has a shorter way for a single rotation. The slice a[-k:] + a[:-k] joins the last k items with the rest, which is the right rotation by k, and it builds a new list. The slice a[k:] + a[:k] gives the left rotation by k. The slices are quick to write, but they copy the list, so they use O(n) extra space. The reversal method keeps the list in place.

The standard library also has collections.deque, a list-like object that can rotate. Its rotate method takes a positive number to rotate right and a negative number to rotate left. It works on a deque, not on a plain list.

Output:

deque.rotate(3): [5, 6, 7, 1, 2, 3, 4]
deque.rotate(-3): [1, 2, 3, 4, 5, 6, 7]

In an interview, you usually cannot use a library call for the problem itself. The interviewer wants to see the reversal method. Knowing the library call still helps, because it lets you check your answer while you practise.

Why this is fast and uses little extra memory

Each reversal touches each item at most once, and each swap moves two items. For a list of length n, the three reversals together do about n swaps in total, so the time grows in proportion to n. The method needs only the variables left, right, n and k, and the swap itself. That is a fixed amount of memory, no matter how long the list is. Computer scientists write this as a rotation in O(n) time and O(1) extra space. The letter n is the length of the list, and the letter O is the notation for how the time grows. You will meet this notation in full in the complexity lesson.

Compare this with the naive method. The naive method shifts every item one place, k times. For a list of length n and a step count of k, it does about n times k moves. When k is close to n, that is roughly n squared moves. The reversal method stays at about n moves, however large k is after the remainder step.

Another method uses a second list. Each item is copied to its new position in a new list, and the new list is used in place of the old one. That method is also O(n) time, but it uses O(n) extra space. The reversal method gives the same time and avoids the extra memory. The task asks for an in-place rotation, so the reversal method is the right answer.

Common mistakes

Forgetting the remainder. If the step count is larger than the length, the reversal ranges go outside the list. Take the rotation function above, remove the line k = k % n, and rotate [1, 2, 3, 4, 5, 6, 7] by 10. Save this as main.py and run it. The program fails with this message:

def reverse(a, left, right):
    while left < right:
        a[left], a[right] = a[right], a[left]
        left += 1
        right -= 1
 
def rotate_right(a, k):
    n = len(a)
    reverse(a, 0, n - 1)
    reverse(a, 0, k - 1)
    reverse(a, k, n - 1)
 
b = [1, 2, 3, 4, 5, 6, 7]
rotate_right(b, 10)
print(b)

Traceback (most recent call last):
  File "main.py", line 14, in <module>
    rotate_right(b, 10)
    ~~~~~~~~~~~~^^^^^^^
  File "main.py", line 10, in rotate_right
    reverse(a, 0, k - 1)
    ~~~~~~~^^^^^^^^^^^^^
  File "main.py", line 3, in reverse
    a[left], a[right] = a[right], a[left]
                        ~^^^^^^^
IndexError: list index out of range

The last frame shows the reversal that failed. The right end was 9, because k - 1 is 9 when k is 10, and the list's last index is 6. The traceback reads from the bottom: the error is on the line in reverse, which was called by rotate_right on line 10, which was called from the main code on line 14. The fix is one line, k = k % n, placed before the reversals.

Using the wrong right end. The helper uses inclusive ends, so the first part of a rotation reverses positions 0 to k - 1, not 0 to k. If you write reverse(a, 0, k), you reverse one item too many. On [1, 2, 3, 4, 5, 6, 7] with k equal to 3, the wrong code gives this output:

[4, 5, 6, 1, 2, 3, 7]

The 7 should have moved to index 2, but it stays at the end. The check is to test a small case by hand, such as length 4 and k equal to 1, and compare the result with what a right rotation should produce.

Swapping the order of the reversals. Reversing the whole list first is part of the method. If you reverse the two parts first and then the whole list, you get a left rotation by k rather than a right rotation by k. For example, the same list with k equal to 3 gives [4, 5, 6, 7, 1, 2, 3] in that order. That is a left rotation by 3, so the code solves a different problem.

Off-by-one when the step count is 0. When k is 0, the first reversal call is reverse(a, 0, -1). The loop does not run, because 0 is not less than -1. So the call is harmless. Some programmers add a special check for 0. That check is fine, but it is not required. Be careful with the negative index, though. The helper never reads a[-1], because the loop test stops it first.

Changing the list when a copy was wanted. The function changes the list you pass in. If the caller needs the original order later, pass a copy. The copy method makes a copy of a list in one call, as in result = a.copy(). The caller can then rotate the copy and keep the original.

Trying to rotate a string in place. A string cannot be changed in place in Python. The reversal helper fails on a string with a TypeError. Convert the text to a list of characters first, with list(text), then join the list back into text with "".join(...), as the practice exercises do.

s = "ForgeStack"
s[0] = "x"

Traceback (most recent call last):
  File "main.py", line 2, in <module>
    s[0] = "x"
    ~^^^
TypeError: 'str' object does not support item assignment

Practice

Exercise 1. Rotate [10, 20, 30, 40] to the right by 1 by hand. Write the list after each of the three reversals. Check the final answer by running the function above.

Show the answer

Step 1 reverses the whole list to [40, 30, 20, 10]. Step 2 reverses the first 1 item, which changes nothing, so the list stays [40, 30, 20, 10]. Step 3 reverses positions 1 to 3, which gives [40, 10, 20, 30]. That is the right rotation by 1. The program prints Right by 1: [40, 10, 20, 30].

Exercise 2. Rotate [1, 2, 3, 4, 5, 6] to the left by 4. Use the fact that a left rotation by 4 is the same as a right rotation by 2 on a list of length 6. Write the answer, then check it with the code.

Show the answer

The left rotation by 4 moves the first four items to the end, which gives [5, 6, 1, 2, 3, 4]. The same answer comes from a right rotation by 2: the last two items, 5 and 6, move to the front. Both ways give [5, 6, 1, 2, 3, 4].

Exercise 3. Use the reverse helper with the three-step method to rotate the text ForgeStack to the right by 3. Convert the text to a list of characters first, and print the result as text.

Show the answer

Output:

ackForgeSt

The last three letters, a, c and k, moved to the front. The helper does not change, because a list of characters works the same way as a list of numbers.

Exercise 4. Write a function that takes a list and a step count, and returns a new list instead of changing the old one. Test it with the list [1, 2, 3, 4, 5] and k equal to 12, and print both the input and the output.

Show the answer

Output:

[4, 5, 1, 2, 3]
[1, 2, 3, 4, 5]

The remainder is 12 % 5, which is 2, so the output is [4, 5, 1, 2, 3]. The input prints as [1, 2, 3, 4, 5], which shows that the caller's list was not changed.

Exercise 5. A student writes this rotation for a list of length n and step count k, where k is already smaller than n:

reverse(a, 0, n - 1)
reverse(a, k, n - 1)
reverse(a, 0, k - 1)

Predict the output for [1, 2, 3, 4, 5] with k equal to 2, then say which kind of rotation it performs.

Show the answer

The first reversal gives [5, 4, 3, 2, 1]. The second reverses positions 2 to 4, which gives [5, 4, 1, 2, 3]. The third reverses positions 0 to 1, which gives [4, 5, 1, 2, 3]. That is the right rotation by 2. The code is correct even though the last two steps are in a different order from the lesson. The two partial reversals touch separate parts of the list, so either one can run first. The first step must still be the reversal of the whole list.

Summary

• A right rotation by k moves the last k items to the front and keeps the order of the others.
• Reverse the whole list, then reverse the first k items, then reverse the rest. The result is the right rotation by k.
• Use k = k % n first, so a large step count becomes a small one and the reversal ranges stay inside the list.
• The method takes about n swaps and uses a fixed number of variables, so it is O(n) time and O(1) extra space.
• A left rotation by k is the right rotation by n minus k, or the same three reversals done in the order: first k, then the rest, then the whole list.