The best part about this video is that she didn't go with the optimized solution from the get-go but rather gradually build up to it explaining all the optimizations.
This is definitely the best explanation i've seen online! Thanks for drawing out and running through an example where each worker has a chance to be the captain. That definitely cleared up all of my confusion. Keep it up!
A very tough question & the way you explained it by starting from the brute force approach & then gradually moving to optimized approach was just awesome, kudos Shiran !! Keep it up :)
Amazing visuals and solid explanation of the intuition. You actually explained why does the ratio of wage/quality matter and how to optimise choosing captian.
The best explanation so far. It's not about the code. As if you are solving or trying hard problems you already know how to write that. What matter here is what is the problem , how to solve the problem and why this approach is best and let me tell you, you nailed the explanation part. You earned a subscriber miss.
Loved the video and the explanations, you rock! I also really liked the fact that contrary to what common sense dictates, the algorithm wouldn't let us choose the best and cheapest worker, since he's skewing everybody's paychecks (שובר את השוק). Keep it up 👸
Most Unique and Nicest Ever explanation seen on UA-cam for a leetcode hard Problem. Thanks a lot. Code Quality Oh My God !!👌 U are killing it there 🔥🔥🔥🔥
Please make a video on Strobogrammatic Number II .. by the way this video was extremely helpful(literally best explanation that can be) video thankyou very much :)..
Hey Shiran, could you please explain that why is discrepancy in the time complexity you mentioned in insertion of heap for the two code blocks. For the code block from line 16 to 19 you told it is O(k) and for 23 to 34 you told it is nlogK, Why is is O(k) although we are inserting in the heap which acutally takes O(log of size of heap). Please explain this. Thanks a lot!
You are so cute and this explanation is so awesome!! Love this!! However, should captainRatio in line 20 be workers[k-1].first? Since I thought k-1 should be captain in the first place. Though its no big deal since the answer is correct lol.
HEy Also ! How are we always sure that there will be a person whi can be the captain of the team (i.e form a team of size k) because even in this example we saw how 2 peoplw were not able to make a team unless we would somehow pay more than his expected wage and make him the captain
That will also work. but the complexity is different. What you suggest has O(n + klogn) time and O(n) space. what i did in the video is O(k + (n-k)logk) time and O(k) space.
@@ShiranAfergan I usually use std::multiset for the heap. Under the hood it's implemented using RB tree so the time complexity would be similar. The great thing about it is that you can pop the last element using minHeap.erase(minHeap.end()--) It also allow you to find an arbitrary element using minHeap.find(). Great explanation btw. I was so lucky to find your channel :)
Because we want the heap to contain the k smallest qualities. Let’s say we have k=3, heap={1,2,4} and current quality is 3. If we were to replace 3 with anything other than the largest quality (4), the heap will not contain the 3 smallest qualities (1,2,3)
@@ShiranAfergan Thank you so much for replying， but what if we have k=3,heap={2,4,5}, and current quality is 3, and there are more elments coming after the current elment, if that's the case, shouldnt we pop out 4 and 5 the elements and push 3 then push 4 again to make {2,3,4} in the heap ? if we only choose the highest quality person to replace, does it mean we have k-1 elements already optimal in the heap ? I am so confused.
Yes, after each iteration, the heap will contain the k smallest elements we have seen up until that point and not necessarily in the whole array. So only when we finish looping over the entire array, the heap will contain the k smallest elements in the array. If you’re still confused, try contradicting this assumption. Start like this - assume that the heap does not contain the k smallest elements. Meaning there is at least one element x, which is one of the k smallest elements but is not in the heap. So either x was never inserted to the heap or it was inserted and later replaced. Can one of these options really happen?
Here is my code: class Solution { public double mincostToHireWorkers(int[] quality, int[] expWage, int k) { double mincost = Double.MAX_VALUE; int n = quality.length; double[][] workers = new double[n][2]; for (int i=0;i Double.compare(a[0], b[0]));
PriorityQueue pq = new PriorityQueue(Comparator.reverseOrder()); double qsum = 0;
![Google Coding Interview Question explained | Course Schedule 2 [LeetCode 210]](http://i.ytimg.com/vi/33vK4AqXjag/mqdefault.jpg)
![Google Coding Interview Question explained | Course Schedule 2 [LeetCode 210]](/img/tr.png)
![Google Coding Interview Question and Answer - Most Stones Removed with Same Row or Column [LeetCode]](/img/n.gif)
The best part about this video is that she didn't go with the optimized solution from the get-go but rather gradually build up to it explaining all the optimizations.
Glad you enjoyed it 😊
This is definitely the best explanation i've seen online! Thanks for drawing out and running through an example where each worker has a chance to be the captain. That definitely cleared up all of my confusion. Keep it up!
That’s awesome! I’m glad it helped :)
Thanks. You really explained great. I was struggling to find a solution like yours. Once again thanks
The code is simple, but this problem is really hard to wrap your head around. She did an incredible job explaining the ratio concept at the start
the best thing about the solution is the math questions ...thank you for the solution
Spent over a day trying to understand the optimized solution.
You made it really simple.
Thank you so much!
This is the best explanation I have seen yet.
Thank you! That’s great to hear:)
This is really one of hardest questions I saw. I could neever even understand the solution without your guidance. Thank you.
Yes, it’s definitely a tough one. I’m glad the video helped:)
A very tough question & the way you explained it by starting from the brute force approach & then gradually moving to optimized approach was just awesome, kudos Shiran !! Keep it up :)
Amazing visuals and solid explanation of the intuition. You actually explained why does the ratio of wage/quality matter and how to optimise choosing captian.
Your explanation is far better than many content on youtube. Please post such odd leetcode problems in such a fantastic way.
Thank you :) I’m working on a new one now. Hopefully will be up next week.
The best explanation so far. It's not about the code. As if you are solving or trying hard problems you already know how to write that. What matter here is what is the problem , how to solve the problem and why this approach is best and let me tell you, you nailed the explanation part. You earned a subscriber miss.
Loved the video and the explanations, you rock!
I also really liked the fact that contrary to what common sense dictates, the algorithm wouldn't let us choose the best and cheapest worker, since he's skewing everybody's paychecks (שובר את השוק). Keep it up 👸
Thanks! Glad you liked it 🙂
Very Nice!! I love the way u start from naive approach to the best solution and optimised the solution step wise .
Most Unique and Nicest Ever explanation seen on UA-cam for a leetcode hard Problem. Thanks a lot. Code Quality Oh My God !!👌
U are killing it there 🔥🔥🔥🔥
Thank you!! 🙏🏽🙏🏽
by your explanation i am able to do 2 question this one and other "maximum performance of a team"(leetcode) .
great explanation . thanks a lot
That’s awesome! 💪🏽😎
wow Just outstanding explaination ! after spending some years people can learn to code but very few get this skill of explaining the code.
Thank you! 😊
Brilliant explanation, You definitely deserves more views. Top quality content
Thanks Priyansh! I’m glad you enjoyed it :)
Thanks for showing the solution that won't work and then improvising. Was easier to connect the dots!
You’re welcome :) I’m glad it helped!
Really liked your way of explaining. Thank you so much for such an explanation. Using a variable named "Captain" was very cool.
Thank you! The leetcode solution also had the “captain” worker so can’t take credit for that name :) glad you enjoyed the video!
Thank you so much! This channel is by far the best I've found on the topic.
Please keep uploading, your videos are among the best on youtube
Thank you! 😊
Explanation is really crisp and detailed. Keep up the good work.
Thank you :)
Best explanantion so far.
I knew this would be the best explanation. thanks
Thanks for the great explanation ! Each time you applied some optimisation I felt like "dayum" . Your naming of variables was also top-notch.
😆 Thank you! I’m glad you enjoyed it 😁
Why you stopped making videos?? This was such a great explanation, pls solve more leetcode questions 😅
Why don't you make a playlist, it would be very helpful. You explained it very nicely. This is best.
Didn’t think of that. I’ll do it, thanks :)
Concise and clear. Thank you Shiran Afergan.
Thanks 😊 glad you liked it
Your Explanation is very nice and good approach .. plz make these type of video continuously
Thanks Rahul! I got one coming up in a few days :)
Great explanation. I really enjoyed the "paper" explanation and process onto code.
Keep it up
That’s awesome! Thanks:)
This explanation makes it so simple! Thanks!
You are great explainer! Loved it! Looking forward to more questions
Very well explained in 15 minutes.
Thanks:)
Thanks a lot for this amazing video @Shiran Afergan!!!!
You’re welcome :) I’m glad you enjoyed it!
Explanation is top notch...keep going.
Thank you :)
YOU'RE THE BESSSTTTT!
Thank you for making it easy to understand.
Thanks 🙏🏽 😊
You look too good to post solutions to leetcode problems * NVM*
:)
excellent explanation!! [best ever]
Brilliant explanation🙂Thanks for sharing
Thank you so much for such a clear explanation.
And wow great solution video !
Thanks!
Please make a video on Strobogrammatic Number II .. by the way this video was extremely helpful(literally best explanation that can be) video thankyou very much :)..
Thank you! That’s great to hear :) i like your suggestion, Haven’t done a video on this type of recursion yet. Adding to my list.
Really good explanation! Thanks.
Thanks 🙏🏽
Awesome explanation!
Your explanation is good...
Thanks!
Thank you so much for this video!
Liked your explanation 👍👍
Thanks for watching :)
Fantastic!
🙂
Very good Explanation
Thanks :)
Brilliant Explaination. Thank you
Well Explained , thank you
Hey Shiran, could you please explain that why is discrepancy in the time complexity you mentioned in insertion of heap for the two code blocks. For the code block from line 16 to 19 you told it is O(k) and for 23 to 34 you told it is nlogK, Why is is O(k) although we are inserting in the heap which acutally takes O(log of size of heap). Please explain this. Thanks a lot!
At 13:15, I liked the video!
You are so cute and this explanation is so awesome!! Love this!!
However, should captainRatio in line 20 be workers[k-1].first? Since I thought k-1 should be captain in the first place. Though its no big deal since the answer is correct lol.
It is! Great catch, it’s a bug that i fixed later in the video (fix is at time: 14:57)
Thank you so much. This is super clear!
I’m glad it helped:)
Great explanation! keep going
Thank you!
that's awesome
HEy Also ! How are we always sure that there will be a person whi can be the captain of the team (i.e form a team of size k) because even in this example we saw how 2 peoplw were not able to make a team unless we would somehow pay more than his expected wage and make him the captain
Thanks!
9:15 Why not just use a minHeap(negative of what you are pushing into the maxheap) and pop the top K?
That will also work. but the complexity is different. What you suggest has O(n + klogn) time and O(n) space. what i did in the video is O(k + (n-k)logk) time and O(k) space.
@@ShiranAfergan I usually use std::multiset for the heap. Under the hood it's implemented using RB tree so the time complexity would be similar. The great thing about it is that you can pop the last element using minHeap.erase(minHeap.end()--) It also allow you to find an arbitrary element using minHeap.find().
Great explanation btw. I was so lucky to find your channel :)
subscribed
please tell me how quickly you were able to come up to this solution ? Amazing!!!!
I don’t remember but I can tell you I highly doubt I’d be able to come up with this during a 45 minutes interview 😆
@@ShiranAfergan thank you, my confidence has lowered after seeing this problem and the way you solved it😅 I was no way I can do this.
Better than the stupid leetcode editorial
Thanks :)
I think this is the hardest one.
Why only compare the quality[k] to quality[n-k] with maxHeap.top() instead of every element in maxHeap ?
so Why do we choose the highest quality person to remove? Why not choosing other workers?
Because we want the heap to contain the k smallest qualities. Let’s say we have k=3, heap={1,2,4} and current quality is 3.
If we were to replace 3 with anything other than the largest quality (4), the heap will not contain the 3 smallest qualities (1,2,3)
@@ShiranAfergan Thank you so much for replying， but what if we have k=3,heap={2,4,5}, and current quality is 3, and there are more elments coming after the current elment, if that's the case, shouldnt we pop out 4 and 5 the elements and push 3 then push 4 again to make {2,3,4} in the heap ?
if we only choose the highest quality person to replace, does it mean we have k-1 elements already optimal in the heap ?
I am so confused.
Yes, after each iteration, the heap will contain the k smallest elements we have seen up until that point and not necessarily in the whole array. So only when we finish looping over the entire array, the heap will contain the k smallest elements in the array.
If you’re still confused, try contradicting this assumption. Start like this - assume that the heap does not contain the k smallest elements. Meaning there is at least one element x, which is one of the k smallest elements but is not in the heap. So either x was never inserted to the heap or it was inserted and later replaced. Can one of these options really happen?
Man !! Effortlessly cute
I hate math problems so much...
who is from May 11th 2024?
Here is my code:
class Solution {
public double mincostToHireWorkers(int[] quality, int[] expWage, int k) {
double mincost = Double.MAX_VALUE;
int n = quality.length;
double[][] workers = new double[n][2];
for (int i=0;i Double.compare(a[0], b[0]));
PriorityQueue pq = new PriorityQueue(Comparator.reverseOrder());
double qsum = 0;
for(int captain = 0;captain k){
qsum -= pq.poll();
}
if(pq.size() < k) continue;
mincost = Math.min(qsum * ratio ,mincost);
}
return mincost;
}
}