Continuing our series on coding interview problems, this week we're tackling rotating a list. This problem is interesting, because there are a number of variables to consider. In which direction should the list rotate? How many places should the items be shifted as part of this rotation? We'll cover everything you need to know in this post.
Walking Through the Problem
To start off, what exactly do we mean when we talk about rotating a list?
Imagine we have a list like this:
base = [1, 2, 3, 4, 5]
If we were to rotate the list one place to the right, we would shift every value right by one place, and the item at the end of the list would wrap around to the front:
right_rotation = [5, 1, 2, 3, 4]
Rotating one place to the left would give us the following instead:
left_rotation = [2, 3, 4, 5, 1]
When rotating a list, the length of the list does not change, and all values are preserved. This is why we end up with this wrapping behaviour, because shifting the list items would otherwise create holes in the list, and items would also end up outside of the valid range of indices for that list.
Let's start with the easiest version of this problem, where we perform a single place rotation like in the examples above. Our initial direction will be a rotation to the right (clockwise).
One thing to consider is that barring the rightmost value, all of our values are in the correct order. This means we don't need to manually perform some action for every single item in the list, and a loop is therefore probably unnecessary.
Instead, for a single place clockwise rotation, we can grab the value of the rightmost list element, store it, and then delete it from the original list. This gets us 90% of the way to a working solution.
We can then concatenate (join together) the original final value and the remainder of the list into a new list: this time in the rotated order.
Let's take a look at that in some code.
A Single Clockwise Rotation
We can start by grabbing the final value of our base list. For now we can just use our example list from the beginning:
base = [1, 2, 3, 4, 5]
final_value = base[-1] # 5
If you're a little confused as to what the -1 means, it's possible to use negative indices in conjunction with sequences, and they work in reverse. So -1 means the last item, -2 means the penultimate item, and so on.
When it comes to removing the item from the original list, we have two main options. If we can guarantee the items are all unique, we can use the remove method:
base = [1, 2, 3, 4, 5]
final_value = base[-1] # 5
base.remove(final_value) # [1, 2, 3, 4]
However, in most cases, you're going to want to use the del keyword instead, since del relies on indices, rather than values, and is therefore less prone to error in this case.
base = [1, 2, 3, 4, 5]
final_value = base[-1] # 5
del base[-1] # [1, 2, 3, 4]
Now, some of you looking at this might have noted that there's a shorter way to do this: the pop method.
If you're not familiar with pop, this method both removes an item from a list, and returns that value. It also works using indices, so it's safe for lists with duplicate elements, and by default it removes the final item. Perfect for our use case.
base = [1, 2, 3, 4, 5]
final_value = base.pop()
Creating the New List
Now that we have our final value separated from the list, we need to combine the items back together. Once again, we have several options here.
First, we can do simple concatenation using the + operator. In this case, we have to convert the final_value to a single item list, since Python won't allow us to concatenate strings and integers.
base = [1, 2, 3, 4, 5]
final_value = base.pop()
rotated_list = [final_value] + base # [5, 1, 2, 3, 4]
Another option is the insert method. insert lets us insert an item at any index we like, so we can place the final_value at position 0 in the base list. One thing to note about this method, is that we don't end up with a new list: we just end up modifying the base list. That may or may not be appropriate for your use case.
base = [1, 2, 3, 4, 5]
final_value = base.pop()
base.insert(0, final_value) # [5, 1, 2, 3, 4]
We can take an almost opposite approach using the extend method. This allows us to append a series of values to a list, by passing in an iterable. It's essentially a multi-value version of the append method.
Once again, we need to convert final_value to a list for this to work.
base = [1, 2, 3, 4, 5]
final_value = base.pop()
rotated_list = [final_value]
rotated_list.extend(base)
An important thing to note about this method is that we don't perform an assignment, so we can't convert final_value to a list on the same line as we use the extend method. This is because [final_value] and final_value are not the same object, and we have no way of referring to the former.
We also can't perform an assignment to get around this, as the return value of extend is None.
A Single Counterclockwise Rotation
Now that we know how to perform a single clockwise rotation, what do we need to change to perform a counterclockwise rotation?
In truth, not a great deal. We can still use pop, and some of our methods for creating the new list work absolutely fine with a few minor tweaks.
With regards to pop, we now need to provide an index as an argument, since we no longer want to pop the final value of the original list: we want the first value instead.
base = [1, 2, 3, 4, 5]
first_value = base.pop(0) # 1
Using concatenation, we now just have to reverse the order of the values like so:
base = [1, 2, 3, 4, 5]
first_value = base.pop(0)
rotated_list = base + [first_value] # [2, 3, 4, 5, 1]
We can also make use of the insert method, but it's also a bit overkill for this situation, since we just want to put first_value at the end. We therefore may as well just use append:
base = [1, 2, 3, 4, 5]
first_value = base.pop(0)
base.append(first_value) # [2, 3, 4, 5, 1]
Getting Fancy
The solutions above are all well and good, but we also have some fancier ways of achieving the same thing. That doesn't necessarily mean they're better, but they're at least interesting to know about.
pop One-Liner
Regarding the solutions above, we can actually accomplish them on a single line. Because pop returns a value, we can put the pop method directly inside the square brackets where we put final_value or first_value. This eliminates the need for the assignment line completely.
Clockwise:
base = [1, 2, 3, 4, 5]
rotated_list = [base.pop()] + base # [5, 1, 2, 3, 4]
Counterclockwise:
base = [1, 2, 3, 4, 5]
rotated_list = base + [base.pop(0)] # [2, 3, 4, 5, 1]
Slices
This is great, but we can be a little fancier than this if we want. We can use slices, for example. If you're not familiar with slicing, I highly recommend you take a look at our previous posts on this topic:
https://blog.tecladocode.com/python-slices/
https://blog.tecladocode.com/python-slices-part-2/
The cool thing about slices is that they don't affect the original list at all. We can also use it on any sequence type, not just lists!
Clockwise:
base = [1, 2, 3, 4, 5]
rotated_list = base[-1:] + base[:-1] # [5, 1, 2, 3, 4]
Counterclockwise:
base = [1, 2, 3, 4, 5]
rotated_list = base[1:] + base[:1] # [2, 3, 4, 5, 1]
Unpacking
A completely different option is available to us using unpacking. Once again, our original list remains untouched, but the syntax here is perhaps a little obscure.
Clockwise:
base = [1, 2, 3, 4, 5]
*head, tail = base
rotated_list = [tail, *head] # [5, 1, 2, 3, 4]
Counterclockwise:
base = [1, 2, 3, 4, 5]
head, *tail = base
rotated = [*tail, head] # [2, 3, 4, 5, 1]
The way this method works is that the * operator will gather up any unassigned values from the multiple assignment.
In the first example, we have two variable names, head and tail, but head is prefaced by the * operator. This means that tail will get a single value (the final value), and head will be assigned the remainder of the list.
We can then create a new list, where tail is placed first, followed by the values in head. So that we don't end up with an entire list as the second element, we can unpack head using the * operator once again. You could just as well use the extend method here if you like, just like we did before.
In the second version, the placement of the * operators is reversed, meaning that head gets a single value, and tail contains the rest of the list.
Deques
One solution we've overlooked so far is the use of the deque collection type. We covered deques in this week's Python snippet, where we showed off its handy rotate method.
The deque collection is part of the collections module, so you'll have to import it in order to use it. Once we've imported the deque type, performing a rotation is as simple as calling the rotate method, and providing a number of places to rotate the sequence by.
Clockwise:
from collections import deque
base = deque([1, 2, 3, 4, 5])
base.rotate() # deque([5, 1, 2, 3, 4]
Couterclockwise:
from collections import deque
base = deque([1, 2, 3, 4, 5])
base.rotate(-1) # deque([2, 3, 4, 5, 1]
Rotating Multiple Positions
So far we've been performing a single place rotation, but we might be asked to rotate a list 3 places clockwise, for example.
If we have the option of using a deque, this is very easy, since we can just provide the number 3 as an argument. However, we're more than likely going to have to implement something ourselves.
We're going to assume that the number of rotations is completely arbitrary, and that the user might request a rotation that exceeds the length of the list. In other words, we'll be allowing for multiple revolutions.
Let's start by defining a function and setting up some initial values:
base = [1, 2, 3, 4, 5]
rotations = 3
def rotate(base_list, r):
pass
To account for multiple revolutions, we can make use of the modulo operator (%) and the length of the list we're rotating. If we divide the number of rotations by the length of the list, the remainder is the the number of rotations we actually need to perform. Everything else represents a full revolution, and is therefore irrelevant.
We do have to be careful here, because modulo will eliminate the sign of r, so we need to perform additional checks in order to preserve it. We'll get to that later.
There's another issue with modulo and negative numbers which we've detailed in another post, so we're going to want to use the abs function to make r positive for this operation.
base = [1, 2, 3, 4, 5]
rotations = 3
def rotate(base_list, r):
rotations = abs(r) % len(base_list)
From here, we can use a for loop to repeatedly perform one of our previous solutions. For example, we might use our pop one-liner solution like so, returning the result.
One thing we have to keep in mind here is that base_list and the global list base are actually one and the same. If we were to pop an item from base_list, base would therefore also be missing an item. This is problematic if we want to run our function multiple times.
To get around this, we can assign a copy of base_list to a variable of the same name. Now when we modify base_list with the pop method, we're modifying a different list object.
base = [1, 2, 3, 4, 5]
rotations = 3
def rotate(base_list, r):
base_list = base_list.copy()
rotations = abs(r) % len(base_list)
for _ in range(rotations):
base_list = [base_list.pop()] + base_list
return base_list
Note that we don't use the current value in range during each iteration, so we can use _ to indicate that the temporary for loop variable isn't being used. range here is just a means of setting a specific number of iterations.
This solution above is fine for positive rotation values, but we haven't accounted for negative rotation values, which require a different concatenation order.
To check for the direction of the rotation, we can use r once again, since r hasn't been altered in any way, and therefore has preserved the original sign of the rotation. If r is less than zero, we know that the user has entered a negative rotation value, and therefore wants to rotate their list counterclockwise.
An if statement is all we need to determine the correct approach:
base = [1, 2, 3, 4, 5]
rotations = 3
def rotate(base_list, r):
base_list = base_list.copy()
rotations = abs(r) % len(base_list)
if r < 0:
for _ in range(rotations):
base_list = base_list + [base_list.pop(0)]
else:
for _ in range(rotations):
base_list = [base_list.pop()] + base_list
return base_list
print(rotate(base, rotations)) # [3, 4, 5, 1, 2]
print(rotate(base, -12)) # [3, 4, 5, 1, 2]
As you can see below, the results are the same as when using the deque type:
deque_1 = deque([1, 2, 3, 4, 5])
deque_1.rotate(3) # deque([3, 4, 5, 1, 2])
deque_2 = deque([1, 2, 3, 4, 5])
deque_2.rotate(-12) # deque([3, 4, 5, 1, 2])
If you'd prefer, you could also write solutions using the other methods we discussed in this post, though I think the version above is relatively simple and readable by comparison.
Wrapping Up
Hopefully you now have a good idea of the various methods you can use to solve a problem like this. As with all coding problems, there are tonnes of solutions available. If you have one that we didn't mention here, we'd love to hear about it, so get in touch on Twitter, or post in our Discord server.
If you're just starting out with Python and want something a bit more comprehensive than these blog posts, our Complete Python Course just got a major refresh on Udemy, with new sections on testing, Selenium, and GUI development. We'd love to have you!
We also have a form to sign up to our mailing list below. It's a great way to keep up to date with all our content, and we also post regular discount codes for our courses just for our subscribers.
