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.

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!