Greedy Algorithm

7 min readMar 24, 2021

Greedy Algorithm

Greed in life can come with stress, anxiety, exhaustion, despair, and depression. It can also lead to a bad lifestyle, and also make a person indulged in Gambling, trickery, and even fraud.

But is greed always bad? It sure can be bad in life but when it comes to programming it is a life savior or I should say it saves a lot of Time, Memory, it increases the Smoothness of the program, Usually finds a solution in linear time(all the programmers know how much it matters).

So what greedy algorithm is? We use the greedy algorithm in a day to day life but unknowingly that it is a greedy algorithm, we follow the necessary steps of the greedy algorithm at every point of our life but we are not aware of the same.

I’ll be taking up a few very basic Examples of few very basic questions that, for sure we all have encountered in our life. After solving those questions we will try to derive the Greedy Algorithm from them. Yes, you read it right, we will not knowingly use a greedy algorithm but the very basic approach we will be using to solve these examples will derive GREEDY ALGORITHM.

Let us Assume a situation, A situation of a let’s say an Interview

The Interviewer has given you this set of 6 numbers, now your task is to form the largest possible number from them.

Different combinations of numbers are possible, right? For example:

159973,975913,3995713…….etc.

But which is the largest number?

The largest number possible is 997531. I know everyone reading this would have had come up with this number as soon as he/she had read the statement. But the question is how did you come up with this solution?

Now lets us focus on the process, not the end product, because the correct answer for this could have been given by anyone, But the process of finding the solution will lead us to a Greedy Algorithm.

What is the largest number that we could possibly form from the given set of numbers, such that we have to use all the numbers 5, 9, 3, 9, 1, 7? This was the problem statement given to us. Let us try to find the largest possible number that can be possible step by step.

This is the list that we have, So the first step that comes to our mind is to look for the maximum number among these numbers.

So step 1 is to Find the largest digit among the given digits.

Now, Step 2 is to Append this number to the new list at the first most significant available position.

Now the last step, remove the number from the original List.

And Now our list looks like this

Now the final step is, To repeat the above 3 steps till the list becomes empty.

The Next Maximum would again be 9, append it to another list and Remove it from the original list

The Next Maximum would 7, append it to another list, and Remove it from the original list

The Next Maximum would 5, append it to another list, and Remove it from the original list

The Next Maximum would 3, append it to another list and Remove it from the original list

The Next Maximum would 1 i.e. the last element, append it to another list, and Remove it from the original list

Now we have achieved the final solution that we wanted that was the largest possible number, with the help of only 3 basic steps

Find Max Digit
Append the number
Remove from the lest
Repeat till all elements are used

Let us now look at another real-life question that will make the concept and more importantly the process much more clear.

You are on a road trip from Point A to B, and your car’s fuel tank has the capacity of running 400 KM in one full tank, there are several fuel stations on your way at different distances, we have to find out the minimum number of refills that are required to reach destination B.

Now One choice could be of first stopping at the fuel station at 200 km, then 550 km then 750 km before finally reaching your destination, In the manner you will need 3 refills. The other could be 375,550,750 and then B which will again take 3 refills

But the optimal solution i.e. the minimum number of refills would be to first stop at 375, then at 750 and finally reaching B this will take 2 refills.

Again most of you would have come across this result but what we need to focus is on the process of finding the solutions.

So let us analyze this process.

THE PROBLEM STATEMENT:

You are in a car, and you need to move from Point A to Point B but the most distance your car could run in one full tank is L km and there are xi fuel station A<n<=B.

A<x1<x2<x3<x4……<xn<=B. Now you need to find the minimum number of refills that you need to move from A to B

So now let us think of a solution for the problem,

In the previous question, we were selecting the largest digit, which was the greedy choice.

Now similarly in this question, we will need to look for a greedy choice,

There are 3 options for the choice

Refill at the nearest possible fuel station
Refill at the Farthest reachable fuel station
Run till you run out of gas.

The third option is obviously wrong, now if we look at the first option we will have to stop at every fuel station in our way which not at all would be optimal, The second option seems appropriate as going till the farthest possible station will not add unnecessary stops

So now we have accomplished our greedy choice.

We will start at A.

We will refill at G, G is the farthest reachable fuel station

Now make G the new A.

The last step can confuse you a bit, but if we think it through you will come to know that it is the very obvious thing. Our Initial journey was from A to B, we refilled at G now we can reduce our problem to going from G to B. And now again find the farthest reachable gas station from G. So not to confuse with the different variable we can easily say that G is our new A or new Source. Now again find minimum refills from G to B.

Now what we did in the problem was that we first made a greedy choice, now after that greedy choice, we reduced our problem to a SUB PROBLEM.

Sub Problem: Same problem of smaller size.

In out First question, largestNumber(9,9,7,5,3,1) = 9+largestNumber(9,7,5,3,1)

Similarly in the second problem, minRefill(A,B)= Refill at G + minRefill(G,B)

So now that we have seen 2 examples and focused on the process of finding the solution and we unknowingly used a greedy algorithm in both of them. So now let us derive what a greedy algorithm is.

1) Make a safe Move: A move is called safe if there is an optimal solution consistent with thisﬁrst move, Not all the first moves are safe. The safe move is also basically the Greedy Choice that we have discussed above.

2) Reduce to SubProblem: First Make a safe move, then reduce the problem to Sub Problem.

3) Repeat: Repeat the process for all elements/till you have reached your destination.

So to summarize the Greedy Strategy or the Greedy Algorithm is: