Greedy Algorithms Tutorial - Solve Coding Challenges

Learn how to use greedy algorithms to solve coding challenges. Many tech companies want people to solve coding challenges during interviews and many of the challenges can be solved using a greedy algorithm. A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage.
✏️ Course from Tanishq Chaudhary. Check out his channel: / tanishqchaudhary1337
Links to coding challenges on InterviewBit:
🔗 Highest product: www.interviewbit.com/problems...
🔗 Bulbs: www.interviewbit.com/problems...
🔗 Disjoint intervals: www.interviewbit.com/problems...
🔗 Largest permutation: www.interviewbit.com/problems...
🔗 Meeting rooms: www.interviewbit.com/problems...
🔗 Distribute candy: www.interviewbit.com/problems...
🔗 Seats: www.interviewbit.com/problems...
🔗 Assign mice to holes: www.interviewbit.com/problems...
🔗 Majority element: www.interviewbit.com/problems...
🔗 Gas station: www.interviewbit.com/problems...
⭐️ Course contents ⭐️
⌨️ (0:00:00) Greedy introduction
⌨️ (0:04:32) Bulbs
⌨️ (0:12:11) Highest product
⌨️ (0:17:08) Disjoint intervals
⌨️ (0:28:43) Largest permutation
⌨️ (0:38:30) Meeting rooms
⌨️ (0:49:25) Distribute candy
⌨️ (1:03:13) Seats
⌨️ (1:19:13) Assign mice to holes
⌨️ (1:24:19) Majority element
⌨️ (1:35:28) Gas station
⌨️ (1:52:39) End
--
🎉 Thanks to our Champion and Sponsor supporters:
👾 Raymond Odero
👾 Agustín Kussrow
👾 aldo ferretti
👾 Otis Morgan
👾 DeezMaster
--
Learn to code for free and get a developer job: www.freecodecamp.org
Read hundreds of articles on programming: freecodecamp.org/news

[@mankritsingh]

A little help for Disjoint interval(I too got stuck on it) When you first see the question,you make make the following observations in the following order 1)We need to select sets without overlap.This is done by observing the start and end 2)As we know how to understand whether there is overlap or not,next we aim to find how to understand which set to take and which to avoid? 3)Now we see one thing that we can select the sets based on thier start,end or length. The length is not practical as a long set may not overlap with any of the element. 4)Now in start and end. Just think that when we look at the next set to add,which element sets the rule/limit? Its obvious that end is setting the limit. 5)Now we have formed the thinking,we will do the code part //code bool compare(vector &v1,vector&v2){ return v2[1]>v1[1]; } int Solution::solve(vector &A) { sort(A.begin(),A.end(),compare); int ans=0,last=0;; for(vector it:A){ if(it[0]>last){ ans++; last=it[1]; } } return ans; }

[@pratikmhatre4815]

Thank you so much for your efforts. And thanx Beau for posting such useful content on this channel

[@shriharikulkarni3986]

Awesome tanishq, need more videos on greedy technique, leetcode problems are still a lot challenging and really struggling to "when to apply" greedy. Please provide more videos and practice problems.

[@andreseriliano1761]

This channel is awesome! Thanks for sharing your knowledge!

[@tanmoy.mazumder]

it’d be so so helpful if there were more videos like this on different topics

[@chaudharycodes]

Glad to know these videos are helpful! I actually plan on doing more topic based interview coding questions. I'll be adding those videos on my channel :)

[@mehulsolanki9435]

Check out the other video from FreeCodeCamp - they have good content on Dynamic Programming, Graphs, and Binary Trees among others.

[@ritwik_shivam]

Amazing and very helpful video, I am daily referring this to learn greedy algorithm concepts, and finding it very trick as well, but your explanation, pace everything is fantastic. One small doubt for 28:51-38:31 largest permutation- def maxSwapsPossible(A,B): i = 0 max_i = len(A) d = {x:i for i, x in enumerate(A)} while B and i

[@aparnakholiya6487]

In the video, the array was first sorted, so the max element will be present in len(A)

[@sparksfly4421]

Since, we want the maximum element's value at the variable, maybe we can use max_i = max(A) as a workaround instead? For eg, A = [2,5,3,4,1]. Dictionary will look like {2:0, 5:1, 3:2, 4:3, 1:4}. (Note: keys in the dictionary are the values of the numbers in list, and their indices are the values here). When we access the d[max_i] key, we get the corresponding value i.e. the index to it, which in this case would be 1 (index of max(A) which is 5). After this we can simply check if this maximum value is at the 0th index and swap their places, as well as their keys in the dictionary and increase the 0th index by 1 as well and continue similarly. right? Also the array needs to have a permutation of all the numbers till len(A), otherwise the code will break.

[@sharadsingh3485]

Wow, so well done! Thanks for posting, man! Very helpful.

[@Mutual_Information]

Fun fact.. in Reinforcement Learning, if you know the optimal value function (which tells you how valuable it is to be in a given state), then the greedy policy with respect to that value function is the globally optimal policy! Sometimes the greedy approach is the best approach :)

[@AnkitKumar-ph6zm]

Mostly epsilon greedy is used for exploration so yeah greedy in the limit with infinite exploration.

[@whoisray1680]

​@@AnkitKumar-ph6zm exactly what I was thinking. In this case "greedy" seems like a misnomer

[@WaldoTheWombat]

11:30 I don't understand why the condition for flipping the bit is if the cost is odd, if the bit was 0 originally and the cost is odd then that means it's 1 now, so why flip it back?

[@tunvirrahman9504]

awesome. Adding this to my playlist

[@bellydancingwithsrishticho7245]

What amazing solutions for all the videos !!! especially for majority element. When you need space o(1) just use bits..wow will always keep this is mind. Thank you 🙏

[@kingmaker9082]

In gas station question, you can avoid extra iteration like keeping condition if start>=n: break Thanks for the amazing tutorial 👍

[@yashkumar9671]

excellent video, thanks for the effort man. Helped me a lot

[@grotsunfull]

Thanks for the content!

[@abdullah-al-wahed]

This was extremely helpful to me ! Thanks a lot

[@eyob7232]

For the majority element problem, I believe the best solution will be to sort the element and pick the middle value since the majority element is the one that occurs more than N/2 times so it is a guarantee that it will sit in the middle of the list.

[@mohdshoaib2507]

sorting array will take NlogN time,, while moore algo take N only.

[@chrisogonas]

Very well illustrated! Thanks

[@ashutoshmodi06]

We don't need to sort the whole array in the highest product question. We can iterate through the list once and find the highest 3 and lowest 2 numbers. And compare the maximum of both solutions. It would reduce the time complexity from O(NlogN) to O(N).

[@joseph2073]

Correct 💯 Maybe he had to explain how to find highest 3 and lowest 2 numbers in an array that's why he skipped it. Like in the same way, he skipped Moore's voting algo in majority element question.

[@ale-hl8pg]

but it wouldn't be a greedy algorithm greedy algorithms boil down to selecting the best option at each iteration imo it's incredibly vague compared to something like dynamic programming which is almost like a specific technique but yeah

[@garvgoel1743]

Hie @tanishq.... Loved the style of your coding. Learnt a lot from your coding style. Thank you❤

[@RestartUPSC2026]

Thanks for the tutorial!

[@universecode1101]

Algorithms are useful to understand better some things ... nice challenge

[@WaldoTheWombat]

11:30 I don't understand why the condition for flipping the bit is if the cost is odd, if the bit was 0 originally and the cost is odd then that means it's 1 now, so why flip it back?

[@karljuhaa9055]

Wow.......That' s so cool. Keep going Sir. TNice tutorials motivtes too.

[@moin.k6351]

That was great. Thank you.

[@matteofioretti8218]

So helpful, really thank you.

[@CauseOfFreedom-mc7fx]

Thanks for this tutorial. I've found it quite helpful during my job search. Only one improvement would be to just simply loop forward and backward once each. I think that's a lot simpler to understand and more space efficient.

[@bhavin6431]

Great video. Thanks

[@chuck_norris]

Great Video! Just in time to lean for my exams

[@sachinbhujel909]

One of the best coding channel in KZbin....

[@scottmclean1011]

Everything works at its best!!

[@akhilbisht798]

Thanku for your efforts this helps a lot

[@agusisas5742]

Great video!

[@vaisakhkm783]

wow yesterday i got homework for greedy algorithm, and here we are

[@jasonguo7596]

Many thanks!

[@abstylegaming]

Thanks for this video

[@yunogasai_uwu4648]

Those visualizations did really help, gg❤

[@Rahul-ur6xz]

Nice Explanation

[@mankritsingh]

Thank you for the video.I have a doubt in Highest product which is at 12:11 . Why are we not handling or looking at the possibilty of overflow here? it is given in question that the answer will be stored in a 32 bit variable so should we not consider that?

[@aydasu]

amazing thank you!

[@mathiinfy3308]

Thanks!!!

[@AnshulSharma-gq2vn]

great content!!

[@YimYamYo]

This came at the perfect time

[@kartiknagrale1479]

Thank you 🙏🏻

[@abdirashidmuhumedomar8594]

so I decided to give soft softs a try. I just subscribed to your channel

[@arjunshinde1255]

Nice work

[@hieuho857]

Nice video!!

[@somdebsar7378]

The bulb problem keep my mind glowing

[@himu1901]

Want to hug you man..Thank you from bottom of my heart.

[@aslam5507]

Thankyou 🙂

[@it_08amanagarwal35]

Excellent Lecture Binary Tree question next

[@youcanyouwill2004]

🎉🎉 amazing

[@lorlox5046]

TNice tutorials is so amazing thanks for the videooo ;D

[@chamathcooray2984]

Please do a course on Divide and Conquer!

[@iitian2034]

thank you so much

[@abdfadee8267]

Thank you

[@rafsanhasan179]

for the higest product we do not need to sort the array. we could just use 5 variable for finding the biggest 3 and the lowest 2. that way the time complexity would be o(n) that is better than O(nlogn).

[@codr0514]

True, but won't scale. Let's say instead of constant 3, multiply M numbers? in such case sort the array and split the M based Even/Odd and try to find max product. Generally interviewers go for such follow up questions, and sorting and finding gives you scalable solution.

[@Vancha112]

Sorry, but I can't imagine myself on a 2d world where voices come from above 😭 All lame jokes aside, awesome stuff, this is really helpful for leetcoders ^^

[@mdborhankhan3559]

Amazing

[@brianmalone6484]

The bulb solution is remarkably unintuitive. Consider the bulbs in groups of similar values (e.g., 1111000 requires one flip; 000000011111 requires two; strict alternation is the worst case, as in 010101010). Then it's obvious you need to locate the first 0, then count the number of cases where a value differs from the preceding. It makes the solution provided by Sheyteo simple to understand, and avoids all the unnecessary modulo operations in the solution provided.

[@rohithbhandari7836]

Yes I could not get it

[@jayg125]

In the candies question, wouldn't it be faster if you iterate once L->R as said earlier and then iterate once R->L and set the value of element to be max of current and candies[i+1] to candies[i] due to most sorting implementations being O(nlogn) in the languages?

[@blackraven6049]

Is there another explanation of the bulbs problem? As in those classic CS problems like the Stable Marriage (Gale-Shapely)?

[@tuskytuts]

in the Largest permutations problem. we have the largest index and length of the array as 5 , if we give any value greater than 5 , will throw an err

[@wilfredomartel7781]

Cool!

[@kristaqvin]

the majority element solution blew my mind

[@kerimgueney]

Great video, but I think the largest permutation problem is not all that well explained. What does "largest permutation" even mean? Is it a permutation that results in the biggest numeric value when all elements are put together (because that's what's implied)? Because if so, then the solution is incorrect.

[@abhinav.srivastava]

For maximum product problem, consider input as [-1,-2,-4,-3,0], both the hypothesis would be 0 and max would again be 0, interesting.

[@mith_jain_here]

Yes, any other combination would give negative answer

[@veto_5762]

In that case the answer is simply is zero, you could even put a clausule to return zero if that's the highest value in the array

[@yuno_that]

Thank you so much❤

[@yuno_that]

1:36:05

[@muscleinjury3331]

yess!

[@pritamsarkar9931]

The highest product problem can also be solvable in Linear O(n) time without sorting but using if else.

[@haomintian6815]

Thank you for the video. But I have a question about Distribute candy problem at 1:02:12. How can you do data = sorted((x,i) for i,x in enumerate(A)) since the value in the array may be duplicated and the key in data needs to be unique.

[@akshitkumar9648]

It is an array of sets. Not a dictionary.

[@gigachad2419]

He really explains in a 3Blue1Brown Way.... Ngl

[@chaudharycodes]

Haha! This is the best compliment I have gotten. Happy that you are liking it. Thanks a lot 😄

[@gigachad2419]

@@chaudharycodes I really mean it though The Dialogues and Animation and the Way you Explain is just Fabulous ❤.. (Btw you seem to be from India...)

[@non5309]

Хорошие разборы задач на алгоритмы и структуры данных, спасибо!

[@gigachad2419]

What if in 3rd problem the max sum of ranges is asked... Instead of max number of intervals What if the Continued ranges were acceptable? Example : { (1, 2), (2, 5), (5, 7) } all can be taken...

[@madhousenetwork]

wow!

[@carlosjacobfield-sierra3759]

I can't wrap my head around "crosses = [(cross-index) for index,cross in enumerate(crosses)]" this part of the Seats problem. Any insights?

[@oceanview3165]

Your light bulb explanation and code is purely ambiguous.

[@mudasssssar2011]

I just download soft soft. Are you using the paid version or the free tutorial one? Because your screen looked way different than mine.

[@abdelhakimlamnaouar9527]

1:17:13 i'm fourteen years old, and the first solution that came to my mind to solve that problem is the mean, but my algo was to find the closest value to the mean hhhhh, and my algo works well.

[@fahidabdullah5637]

I had a question. Regarding problems where you need to find min cost to do something, or min operations, or some similar variant, how do you know that the algorithm you choose guarantees the minimum? I'm sorry if that doesn't make sense but I realize I always second guess on if the algorithm I implement can truly minimize the cost needed? Is there a way to get better at this besides just gaining more experience?

[@eshabanu]

If they ask us in the question to find minimum, maximum, possible no of ways we need to first choose greedy algorithm or recursion

[@manitejachinni5863]

Sir now I am pursuing integrated mtech 5 years course specialization in data science now I completed 3rd can you please say how to and how much I need to prepare to get decent job as fresher in data science sector because there are vast number of topics I am very confused like upto how many concepts I need to cover as a fresher to get decent job in data science sector

[@bilalahmedkhan5876]

What a coincidence! I was just about to start practicing Greedy Algo problems on Leetcode. Thank you for this video freecodecamp!

[@chaitanyaj4877]

Me too, man!

[@ayoubelhioui2205]

the same here, many thanks to him.

[@WaldoTheWombat]

11:30 I don't understand why the condition for flipping the bit is if the cost is odd, if the bit was 0 originally and the cost is odd then that means it's 1 now, so why flip it back?

[@dmytrokorbanytskyi1586]

12:30 - using heapq the task "max product" will work faster

[@Karthikeyan_11K]

My solution for the bulbs problem - def bulbs(A): cost = 0 flip = 0 for i in A: if flip == i: cost += 1 flip = flip + 1 & 1 return cost

[@lonen3rd]

For the Largest Permutation problem, would this solution be considered greedy? def max_perm(arr, B): i = 0 if len(arr) > 1: while B and i < len(arr): max_val = max(arr[i:]) max_val_idx = arr.index(max_val) if arr[i] < max_val: arr[i], arr[max_val_idx] = arr[max_val_idx], arr[i] i += 1 B -= 1 return arr

[@alsr15]

[Majority Element] I want to ask: If I put an array of [1,3,2,4,2,4,4], it incorrectly returns "0". Another example: an array of [1,3,2,4,6,2,4] incorrectly returns "2", although it's not the majority. Could you give some insights? Thanks

[@hi_manshu]

@Tanishq Chaudhary in the Gas Station problem. As you explained, we will move from indices 4 -> 0 -> 1 -> 2-> 3 -> 4. But can we move from index 1->0->4->3->2->1 . Will there be two possible answers? Please explain.

[@BruceNJeffAreMyFlies]

You could do that, but the answer would be different depending how you consider the problem. In reality, the distance between 3 and 4 would be represented by the cost '9', but if you ran the equation backward then you would be assigning that same distance (being travelled backward) only cost '1' because that is the cost being applied to index 4. If you run the equation with the same costs, despite the fact that this would not represent reality, then yes. That would be an alternative solution, though I doubt it would be considered a different solution, by many programmers, because they are so similar.

[@jnsound2962]

ভালো একটা ভিডিও

[@hamza77v]

🔥

[@Moderator.]

We used to study it in 2002..

[@coldheartedhustlers3963]

THANK YOUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU

[@mai_allstar]

yes

[@marcelemontalvao870]

👏👏👏👏

[@justsurajp]

For the largest permutation if input is [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] with swap = 1 the code would swap out 1 and 10, and would yield output [10, 2, 3, 4, 5, 6, 7, 8, 9, 1] which is actually a smaller permutation. Or am I missing something here?

[@a6hiji7]

That's correct. Even if we take [1, 2, 9, 10] and 1 swap, the output will be [10, 2, 9, 1] which is smaller than [9, 2, 1, 10].

[@a6hiji7]

Actually in this problem, largest means largest lexicographical value, not the largest numeric value.

[@ratnadeepsimhadri3465]

@@a6hiji7 So We are supposed to compare the elements of the array lexicographically ?

[@a6hiji7]

@@ratnadeepsimhadri3465 No, comparisons are done numerically, as shown in the video. However, the method leads to the largest lexicographical value possible, not the largest number possible.

[@saifsd8267]

@@a6hiji7 how is [10,2,9,1] lexicographically greater than [9,2,1,10]? It is the other way around.

[@ajith4249]

Could you please correct the problem statement at 50:03 .It is NOT """Children with a higher rating than their neighbors get more candies. "" It should be """Children with a higher rating get more candies than their neighbors."""

[@01aniruddhaislam26]

where is the link to written article on the proof ? 28:46

[@Daividwu]

Mylosp just a legend really aren’t ya

[@psg9278]

👍👍

[@thunder7360]

regular expressions course please

[@Travelophile]

why for distribute candy we didnt sort the array and increase one by one for finding sum ?

[@pashambhupalreddy5429]

12:13 why b%2 ==1 We can use b==1 right ????? Any specific reason to use it

[@Damian-cd2tj]

Just wanted to thank you for your effort, as you asked in 18:45 :)