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.

Links to coding challenges on InterviewBit:

⭐️ 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

--

[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<int> &v1, vector<int>&v2){
return v2[1]>v1[1];
}
int > &A) {
sort(A.begin(), A.end(), compare);
int ans=0, last=0;;
for(vector<int> it:A){
if(it[0]>last){
ans++;
last=it[1];
}
}
return ans;
}

[pratikmhatre]

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

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

[tanmoy.mazumder]

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

[ashutoshmodi]

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).

[shriharikulkarni]

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.

[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<len(A):
j = d[max_i]
if i==j:
pass
else:
B-=1
A[i], A[j]=A[j], A[i]
d[A[i]], d[A[j]] = d[A[j]], d[A[i]]
i+=1
max_i-=1
return A
# For input A = [4, 5, 2, 1], B = 2
print(maxSwapsPossible([4, 5, 1, 2], 2)) #is giving key error, may be because you already fixed max_i = len(A) and it is not really necessary that max element will me at that position.

[eyob]

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.

[universecode]

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

[andreseriliano]

This channel is awesome! Thanks for sharing your knowledge!

[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.

[brianmalone]

The bulb solution is remarkably unintuitive. Consider the bulbs in groups of similar values (e.g., 1111000 requires one flip; 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.

[sachinbhujel]

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

[CauseOfFreedom-mcfx]

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.

[vaisakhkm]

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

[rafsanhasan]

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).

[kingmaker]

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

[bellydancingwithsrishticho]

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 🙏

[yunogasai_uwu]

Those visualizations did really help, gg❤

[ajith]

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."""