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: