Thread by @svpino

Greedy algorithms are super useful!

(And I mean in real life, not only for coding interviews!)

You are probably using them already, even if you don't know it, so let's explore how they work and —more importantly— when they don't.

🧵👇

Here is the gist of a greedy algorithm: it builds a solution using the best option at every single step.

Here is the intuition (for when they work): "if we make the optimal option at every step, we will end up with the optimal solution overall."

👇

An example:

How do you make 73 cents using the least amount of coins? In the US, you will do the following:

▫️2 x 25 cents
▫️2 x 10 cents
▫️3 x 1 cent

At every step, I selected the larger denomination that fit.

This was a greedy solution. It's also the optimal solution.

👇

Another example:

You want to maximize the number of movies you can watch at the theater. You know the start and end time of each movie.

Using a greedy algorithm you can get the optimal solution: at every step watch the movie that ends the earliest.

👇

Greedy algorithms are intuitive and very simple to implement.

However, they always don't give you the optimal solution!

Before deciding on whether a greedy algorithm is what you want, you need to understand whether your solution is optimal or not!

👇

Imagine that we want to find the path on the tree that produces the largest sum.

A greedy algorithm will select 10 + 20 + 40 for a total of 70.

However, the optimal solution is 10 + 1 + 100 for a total of 111!

Here, greedy is not good.

👇

The Knapsack is another classic problem where a greedy approach will not give you the optimal solution.

By the way, this problem is a classic! You want to look at it because you'll hear about Knapsack all the time. Here is the link: en.wikipedia.org/wiki/Knapsack_…

👇

Let me give you a few more examples where a greedy approach is used with optimal results:

▫️Dijkstra's algorithm
▫️Prim's algorithm
▫️Huffman coding
▫️Optimal merging
▫️Topological sort
▫️Kruskal algorithm

Pretty nice, huh?

👇

To close the thread, keep this in mind:

Coming up with a greedy approach is very simple, but proving that your greedy approach gives you an optimal solution is really hard!

Be careful.

🤓