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
For time complexity, there’s not much we can do. Rotations could encompass the list, requiring us to iterate approximately
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
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']
It’s always harder to optimize, so don’t get discouraged!
Write a function
rotate(), with the parameters
rotate() should return the same input list rotated