# 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):

1. What is a greedy algorithm?

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.

2. Are greedy algorithms fast?

Greedy algorithms are generally considered quick and often give good approximations to the optimum.

3. Do greedy algorithms consistently find the globally optimal solution?

No, greedy algorithms do not consistently find the globally optimal solution.

4. What is the paradigm behind the greedy algorithm concept?

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.

5. Where can I learn about greedy algorithms?

You can learn more about greedy algorithms in the free 2-hour course Introduction to Algorithms in Python on RealToughCandy.io. In the greedy algorithms section you will also be given three coding challenges including Assign Mice to Holes.