Greedy Algorithms Tutorial - Solve Coding Challenges
Рет қаралды 311,115
Күн бұрын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; }
@shriharikulkarni3986 2 жыл бұрын
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.
@pratikmhatre4815 Жыл бұрын
Thank you so much for your efforts. And thanx Beau for posting such useful content on this channel
@andreseriliano1761 2 жыл бұрын
This channel is awesome! Thanks for sharing your knowledge!
@tanmoy.mazumder 2 жыл бұрын
it’d be so so helpful if there were more videos like this on different topics
@chaudharycodes 2 жыл бұрын
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 2 жыл бұрын
Check out the other video from FreeCodeCamp - they have good content on Dynamic Programming, Graphs, and Binary Trees among others.
@sharadsingh3485 Жыл бұрын
Wow, so well done! Thanks for posting, man! Very helpful.
@kingmaker9082 Жыл бұрын
In gas station question, you can avoid extra iteration like keeping condition if start>=n: break Thanks for the amazing tutorial 👍
@ritwik_shivam 2 жыл бұрын
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 11 ай бұрын
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.
@tunvirrahman9504 2 жыл бұрын
awesome. Adding this to my playlist
@grotsunfull 2 жыл бұрын
Thanks for the content!
@Mutual_Information 2 жыл бұрын
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 2 жыл бұрын
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 4 ай бұрын
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?
@bellydancingwithsrishticho7245 2 жыл бұрын
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 🙏
@ashutoshmodi06 2 жыл бұрын
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
@abdullah-al-wahed 2 жыл бұрын
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 11 ай бұрын
sorting array will take NlogN time,, while moore algo take N only.
@yashkumar9671 7 ай бұрын
excellent video, thanks for the effort man. Helped me a lot
@RestartUPSC2026 Жыл бұрын
Thanks for the tutorial!
@chrisogonas 5 ай бұрын
Very well illustrated! Thanks
@moin.k6351 2 жыл бұрын
That was great. Thank you.
@universecode1101 2 жыл бұрын
Algorithms are useful to understand better some things ... nice challenge
@WaldoTheWombat 4 ай бұрын
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?
@vaisakhkm783 2 жыл бұрын
wow yesterday i got homework for greedy algorithm, and here we are
@karljuhaa9055 2 жыл бұрын
Wow.......That' s so cool. Keep going Sir. TNice tutorials motivtes too.
@garvgoel1743 Жыл бұрын
Hie @tanishq.... Loved the style of your coding. Learnt a lot from your coding style. Thank you❤
@gigachad2419 2 жыл бұрын
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...
@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?
@chuck_norris 2 жыл бұрын
Great Video! Just in time to lean for my exams
@bhavin6431 2 жыл бұрын
Great video. Thanks
@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 3 ай бұрын
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.
@CauseOfFreedom-mc7fx 29 күн бұрын
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.
@matteofioretti8218 Жыл бұрын
So helpful, really thank you.
@agusisas5742 Ай бұрын
Great video!
@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
@somdebsar7378 11 ай бұрын
The bulb problem keep my mind glowing
@sachinbhujel909 2 жыл бұрын
One of the best coding channel in KZfaq....
@jasonguo7596 2 жыл бұрын
Many thanks!
@abstylegaming 2 жыл бұрын
Thanks for this video
@aydasu 2 жыл бұрын
amazing thank you!
@akhilbisht798 Жыл бұрын
Thanku for your efforts this helps a lot
@Rahul-ur6xz 2 жыл бұрын
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?
@scottmclean1011 2 жыл бұрын
Everything works at its best!!
@kartiknagrale1479 3 ай бұрын
Thank you 🙏🏻
@yunogasai_uwu4648 Ай бұрын
Those visualizations did really help, gg❤
@YimYamYo 2 жыл бұрын
This came at the perfect time
@himu1901 2 жыл бұрын
Want to hug you man..Thank you from bottom of my heart.
@pritamsarkar9931 9 ай бұрын
The highest product problem can also be solvable in Linear O(n) time without sorting but using if else.
@AnshulSharma-gq2vn 4 ай бұрын
great content!!
@blackraven6049 Жыл бұрын
Is there another explanation of the bulbs problem? As in those classic CS problems like the Stable Marriage (Gale-Shapely)?
@mathiinfy3308 Жыл бұрын
Thanks!!!
@arjunshinde1255 Жыл бұрын
Nice work
@kerimgueney 2 жыл бұрын
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.
@chamathcooray2984 2 жыл бұрын
Please do a course on Divide and Conquer!
@hieuho857 Жыл бұрын
Nice video!!
@abdirashidmuhumedomar8594 Жыл бұрын
so I decided to give soft softs a try. I just subscribed to your channel
@kristaqvin Жыл бұрын
the majority element solution blew my mind
@youcanyouwill2004 3 ай бұрын
🎉🎉 amazing
@aslam5507 Жыл бұрын
Thankyou 🙂
@lonen3rd 9 ай бұрын
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
@abdfadee8267 9 ай бұрын
Thank you
@iitian2034 2 жыл бұрын
thank you so much
@brianmalone6484 2 жыл бұрын
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 4 ай бұрын
Yes I could not get it
@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?
@WaldoTheWombat 4 ай бұрын
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?
@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
@it_08amanagarwal35 2 жыл бұрын
Excellent Lecture Binary Tree question next
@mdborhankhan3559 2 жыл бұрын
Amazing
@wilfredomartel7781 2 жыл бұрын
Cool!
@lorlox5046 2 жыл бұрын
TNice tutorials is so amazing thanks for the videooo ;D
@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
@dmytrokorbanytskyi1586 2 жыл бұрын
12:30 - using heapq the task "max product" will work faster
@abdelhakimlamnaouar9527 10 ай бұрын
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.
@manitejachinni5863 2 жыл бұрын
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
@mudasssssar2011 2 жыл бұрын
I just download soft soft. Are you using the paid version or the free tutorial one? Because your screen looked way different than mine.
@Travelophile 3 ай бұрын
why for distribute candy we didnt sort the array and increase one by one for finding sum ?
@yuno_that 11 ай бұрын
Thank you so much❤
@yuno_that 11 ай бұрын
1:36:05
@haomintian6815 2 жыл бұрын
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.
@oceanview3165 Жыл бұрын
Your light bulb explanation and code is purely ambiguous.
@hallelujah_japan 2 жыл бұрын
Please teach us how to building "meetup app".
@michaelguo6349 5 ай бұрын
How is the first solution to the first question gives the minimal number? the algorithm here basically run through the all the bulbs , but that does not prove it is minimum
@Karthikeyan_11K 7 ай бұрын
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
@abumajhool145 2 жыл бұрын
Is there a book on greedy algorithms?
@anazdravkovic3536 3 ай бұрын
In the disjointed intervals problem u made a mistake by always setting value of ending interval to previous value of ending interval, instead it should be like prevEnd = max(prevEnd , currentEnd), correct me if i am wrong
@muscleinjury3331 2 жыл бұрын
yess!
@user-ut4sj7es5b 6 ай бұрын
but what if the array is like:(4,3,2,1,0) and u should raplace 3 time to get the maximum? its will not work.
@hi_manshu 2 жыл бұрын
@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 2 жыл бұрын
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.
@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 ^^
@ajith4249 10 ай бұрын
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."""
@fahidabdullah5637 9 ай бұрын
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 7 ай бұрын
If they ask us in the question to find minimum, maximum, possible no of ways we need to first choose greedy algorithm or recursion
@madhousenetwork 2 жыл бұрын
wow!
@Moderator. 2 жыл бұрын
We used to study it in 2002..
@PIRAISUDANB 7 ай бұрын
distribute candy of time complexity O(n) solution. class Solution: # @param A : list of integers # @return an integer def candy(self, a): ans=[1]*len(a) for i in range(1,len(a)): if a[i]>a[i-1]: ans[i]=ans[i-1]+1 for i in range(len(a)-2,-1,-1): if a[i]>a[i+1]: ans[i]=max(ans[i],ans[i+1]+1) return sum(ans)
@gigachad2419 2 жыл бұрын
He really explains in a 3Blue1Brown Way.... Ngl
@chaudharycodes 2 жыл бұрын
Haha! This is the best compliment I have gotten. Happy that you are liking it. Thanks a lot 😄
@gigachad2419 2 жыл бұрын
@@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...)
@pashambhupalreddy5429 Жыл бұрын
12:13 why b%2 ==1 We can use b==1 right ????? Any specific reason to use it
@01aniruddhaislam26 Жыл бұрын
where is the link to written article on the proof ? 28:46
@non5309 2 жыл бұрын
Хорошие разборы задач на алгоритмы и структуры данных, спасибо!
@hkomsi284 2 жыл бұрын
Jefferson Sales done a few but not there yet
@justsurajp 2 жыл бұрын
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 2 жыл бұрын
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 2 жыл бұрын
Actually in this problem, largest means largest lexicographical value, not the largest numeric value.
@ratnadeepsimhadri3465 2 жыл бұрын
@@a6hiji7 So We are supposed to compare the elements of the array lexicographically ?
@a6hiji7 2 жыл бұрын
@@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 2 жыл бұрын
@@a6hiji7 how is [10,2,9,1] lexicographically greater than [9,2,1,10]? It is the other way around.
@coldheartedhustlers3963 2 жыл бұрын
THANK YOUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU
@mai_allstar Жыл бұрын
yes
@zebra00024 10 ай бұрын
I appreciate your effort, thank you. However is that only me finding problem statements very confusing? IMO Examples should visualize, not define problem statement. Find "the largest permutation possible" is very confusing
Garena Free Fire Global
Рет қаралды 42 МЛН
Tech With Nikola
Рет қаралды 629 М.