Learn

Optimizing a solution means reducing the memory required (space complexity), or reducing the number of instructions the computer must execute (time complexity).

Sometimes this means entirely rethinking the approach to a question and it’s always meant to be a difficult task.

In the last exercise we created a new list using the slice operator. This requires `O(N)` space, because a new list is made with copies of each value, and `O(N)` time because every value is visited while copying. `N` represents the number of values in the list.

We need to do better than `O(N)`.

For time complexity, there’s not much we can do. Rotations could encompass the list, requiring us to iterate approximately `N` times.

For space complexity, we can optimize by constructing in-place solutions, meaning we don’t create any additional data structures for storing values.

Single variable declarations are considered `O(1)`, or constant space, because we’re not allocating memory in relation to the input.

This example function adds `"!"` to each string in a list.

``````def constant_space(list_of_strings):
# variable the same regardless of input
exclamation = "!"
for element in list_of_strings:
element += exclamation

# input mutated but no more space used
return list_of_strings

def linear_space(list_of_strings):
exclamation_list = [] # new structure
exclamation = "!"

for element in list_of_strings:
# adding a new value each loop
exclamation_list.append(element + exclamation)

# holds as many new values as the input!
return exclamation_list   ``````

Given a list and a positive integer, return the same list “rotated” a number of times that match the input integer. This time, we’ll rotate the list backward and use `O(1)` space.

``````list = ['a', 'b', 'c', 'd', 'e', 'f']
rotate(list, 1)
# ['b', 'c', 'd', 'e', 'f', 'a']
rotate(list, 4)
# ['e', 'f', 'a', 'b', 'c', 'd']``````

### Instructions

1.

It’s always harder to optimize, so don’t get discouraged!

Write a function `rotate()`, with the parameters `my_list` and `num_rotations`.

`rotate()` should return the same input list rotated `num_rotations` backward.