What is a greedy algorithm? (Greedy algorithms explained)

What is a greedy algorithm?

Why do software engineers use them?

In this post, you’ll discover the definition of a greedy algorithm.

Then you’ll see it in action with a coding challenge called Assign Mice to Holes.

At the end of the day, understanding greedy algorithms can help you become a more efficient problem solver (and help you pass those FAANG interviews!).

---

Side note: Apparently, if you Google “greediest person”, a real live person pops up.

Can you imagine Googling “the worst person in the world” and your face gets blasted on the screen?

Now, I’m not going to show you who this person is, because I don’t know who he is and it’s not really that important (just kind of funny) but it does tie in with our algorithm.

❓ What is greed to you?

❓ What is a “greedy” approach?

If your beautiful old granny bakes a pie for your family and your uncle Bob shows up (you know, Amy’s ex-husband) and takes the biggest piece of the pie for himself… That would be pretty greedy wouldn’t it?

By him eating the largest portion, that sure would make the
pie easier to finish.

It wouldn’t be great for everyone else and their rumbling
tummies, of course.

But by taking the biggest portion out first, it leaves just little portions to take care of… and this is very similar to the concept that fuels greedy algorithms!

The paradigm behind the greedy algorithm concept is that it builds up a solution piece by piece…Always choosing the next piece that offers the most obvious and immediate benefit.

By using several iterations (and by obtaining the best result) at a certain iteration the result should be computed.

Simply stated, a greedy algorithm is an algorithm that solves a problem by making the locally optimum choice at each stage with the hope of finding the global optimum.

All that said, greedy algorithms do not consistently find the globally optimal solution.

That’s because – generally speaking – they don’t operate exhaustively on all the data.

Nevertheless, greedy algorithms can be useful because they are quick and often give good approximations to the optimum.

If a greedy algorithm can be proven to yield the global optimum for a given problem class, it typically becomes the method of choice.

---

GREEDY ALGORITHM CODING CHALLENGE: ASSIGN MICE TO HOLES

A really fun problem we can solve using a greedy algorithm is known as Assign Mice to Holes.

In this challenge, we need to put every mouse to its nearest hole to minimize the time.

The first thing we should do is sort the positions of the mice and holes first.

That would be pretty greedy of us, wouldn’t it? bruhahahahaaaa 👹

This allows us to put the ith mice to the corresponding hole in the holes list.

We can then find the maximum difference between the mice and corresponding hole position.

Now, does being greedy always equate to a “maximum” of something regarding problem solutions?

Not necessarily.

Another problem that I would encourage you to learn on your own (I triple dog dare you) is the Kids with the Greatest Number of Candies using the greedy approach.

This is considered “easy.”

However, the flip side to this problem is there is a connecting problem asking for the distribution of the minimum number of candies that can be given.

And it’s still wanting the greedy approach as opposed to brute force.

So, again, “greedy” doesn’t always equal “maximum”.

In the minimum distribution problem, brute force would be a one by one distribution of candies to each child until the condition satisfies.

Yet, the greedy way would be to traverse the array just twice… From beginning to end and back to the beginning – while greedily determining the minimum number of candies required by each child.

What Is a Greedy Algorithm? (Conclusion)

Greedy algorithms are useful in countless problem solving scenarios.

Whether you encounter them on LeetCode or find yourself needing to implement one at your real-world software engineer role, this type of algorithm should not be overlooked.

As mentioned earlier, greedy algorithms are generally considered quick and often give good approximations to the optimum.

Want to learn greedy algorithms in depth?

Check out this free 2-hour Introduction to Algorithms in Python course where this lesson continues!

You’ll code out a greedy algorithm for 3 coding challenges (including Assign Mice to Holes):

Software engineers asking what is a greedy algorithm? are also reading:

• AlgoMonster Review
• Best Way to Learn Algorithms
• 18 All-Time Best Books for Data Structures
• 11 Best Algorithms Books
• Grokking the Coding Interview Review