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
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
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 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
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 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
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
base = [1, 2, 3, 4, 5] first_value = base.pop(0) base.append(first_value) # [2, 3, 4, 5, 1]
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.
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
first_value. This eliminates the need for the assignment line completely.
base = [1, 2, 3, 4, 5] rotated_list = [base.pop()] + base # [5, 1, 2, 3, 4]
base = [1, 2, 3, 4, 5] rotated_list = base + [base.pop(0)] # [2, 3, 4, 5, 1]
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:
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!
base = [1, 2, 3, 4, 5] rotated_list = base[-1:] + base[:-1] # [5, 1, 2, 3, 4]
base = [1, 2, 3, 4, 5] rotated_list = base[1:] + base[:1] # [2, 3, 4, 5, 1]
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.
base = [1, 2, 3, 4, 5] *head, tail = base rotated_list = [tail, *head] # [5, 1, 2, 3, 4]
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 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.
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
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.
from collections import deque base = deque([1, 2, 3, 4, 5]) base.rotate() # deque([5, 1, 2, 3, 4]
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 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.
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_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.
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.
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!
Be sure to check back next week for another set of Python posts!