Optimization

In this section, we will explore some code optimization concepts to solve some more challenging problems.

The key to being able to optimize your code is to have a good understanding of computational complexity. If you have not already mastered this subject it is recommended that you take a look at the Computational Complexity.

Selecting the data structure

In the previous lecture, we learned how using the set data structure can reduce your code from to . Using the right data structure in the right way is essential to building more efficient code.

During the exercises try to think if one of the structures you have learned so far can help you make your solution more efficient.

Pre-processing

Another common technique is preprocessing. The idea here is to precompute some values, and then use those values to compute the final solution. Let's understand this idea better with a practical example:

Given a matrix . Find the position such that the sum of all elements of row and column is as small as possible.

To find this position we can go through each position and calculate the sum of row and column , exactly as it is described in the statement. However, this solution results in an algorithm with complexity .