Please do like & share with your friends or other coding communities, ifff and only if you like our videos & want us to make more such regular editorials. Your motivation to watch these videos is to get high package jobs & my motivation is your love ❤
one doubt @ 24:07 Since we're using the ratio of the new quantity, that quantity should be part of the quantitySum.. suppose the heap size > k and the new quantity is the greatest say 5 and we need to remove it.. in that case, what if we remove it from the heap & qualitySum and just use it's ratio?
That is an awesome question, firstly hats off to even think in such deep🫡 . But my claim is : if quality is high of curRatio that we will have to ultimately remove from priority queue, then it will never contribute to minAns. . . Conclusion: thus including or excluding this ratio will never even matter for our ans . . Proof: Also proof is purely mathematically but i’ll explain with an example ( making this example generic ) . . Step1- as all ratios are sorted thus number these ratios as r1, r2, r3, r4. Now as they are sorted just assign them random but sorted values. r1 = 1, r2 = 2, r3 = 3, r4 = 4 (you can take any ratio values but sorted) Step 2 - now we imagine we had to take 2 employees, and also imagine you are at 4th employee i.e. index = 3 (4th employee) Step 3 - (Assumption to prove the fact) - Now we are saying the ith employee has higher quality & we already have lesser k qualities in the heap. Okay, lets say ith employee has quality 5, while you already had in the heap quality of 2 & quality of 1 (imagine for index 1 & 2 respectively) Step 4 - Now as ratios are sorted in ascending order and index3 employee had a ratio of 4 (r4 = 4) and quality as 5 (just considered higher than 2 & 1), so wage which i'll be giving this 3rd index employee will be 5 * 4 = 20$ Step 5 - While if we already had a quality of 2 (taking max quality out of 2 & 1), and we also know its ration will for sure be less than 3rd employee (assumed ratio was 2), thus his wage will be 2*2 = 4 (same will follow for second employee too) Thus, it proves, that as ratios are sorted in ascending order, this will make sure we take minRatio & multiply by minQualitySum to get minPaidSalary to these k employees. I hope this solves the doubt.
The simple explanation is that if we removed the person and used his ratio, that means we are using a higher ratio (since sorted) in the current iteration, but using the quality from last iteration. This will never be minimum than the previous ans and won't matter in the end
Amazing explaination , Didn't imagine I will completely understand hard problem in 1 go. I know I am asking for lot but can you make a giude on how should I follow your intution building playlists becoz questions are arranged in cronological order and some questions are difficult to understand at first
That is an awesome question, firstly hats off to even think in such deep🫡 . But my claim is : if quality is high of curRatio that we will have to ultimately remove from priority queue, then it will never contribute to minAns. . . Conclusion: thus including or excluding this ratio will never even matter for our ans . . Proof: Also proof is purely mathematically but i’ll explain with an example ( making this example generic ) . . Step1- as all ratios are sorted thus number these ratios as r1, r2, r3, r4. Now as they are sorted just assign them random but sorted values. r1 = 1, r2 = 2, r3 = 3, r4 = 4 (you can take any ratio values but sorted) Step 2 - now we imagine we had to take 2 employees, and also imagine you are at 4th employee i.e. index = 3 (4th employee) Step 3 - (Assumption to prove the fact) - Now we are saying the ith employee has higher quality & we already have lesser k qualities in the heap. Okay, lets say ith employee has quality 5, while you already had in the heap quality of 2 & quality of 1 (imagine for index 1 & 2 respectively) Step 4 - Now as ratios are sorted in ascending order and index3 employee had a ratio of 4 (r4 = 4) and quality as 5 (just considered higher than 2 & 1), so wage which i'll be giving this 3rd index employee will be 5 * 4 = 20$ Step 5 - While if we already had a quality of 2 (taking max quality out of 2 & 1), and we also know its ration will for sure be less than 3rd employee (assumed ratio was 2), thus his wage will be 2*2 = 4 (same will follow for second employee too) Thus, it proves, that as ratios are sorted in ascending order, this will make sure we take minRatio & multiply by minQualitySum to get minPaidSalary to these k employees. I hope this solves the doubt.
I am constantly learning new things from your videos thats why I am able to think in depth. Thank you for these awesome videos bro and awesome explanation too :)
Can anyone help me with this part? I get it that we will find the minimum pay by sorting the ratios and maintaining a priority queue to get the min qualities, but what if that total cost that we found didn't meet the minimum wage expectation of one or more people?
We are taking values which are behind the current index and the array is sorted based so for ith element either we will pick its own ratio or a ratio bigger than its ratio which will eventually give more than its min wage
i am not getting one thing , In the code how am i making sure that i do not pick someone such that the ratio*quality of that person is lesser than his minimun wage ??
Since we are sorting by w/q ratio,if we use w/q ratio for a quality values corresponding to higher w/q ratio,we will see that the wage for the person with high w/q ratio will go below his minimum wage value,and so this condition has to be true for every person whose w/q ratio we are looking to check.
![Google Coding Interview Question and Answer - Min Cost To Hire K Workers [LeetCode 857]](http://i.ytimg.com/vi/o8emK4ehhq0/mqdefault.jpg)
![เปิดคำทำนาย นอสตราดามุส - บาบา วานก้า ปี 2025 คนทั่วโลกต้องเจออะไรบ้าง? | แฉ 11 ธ.ค. 67 [2/3] |GMM25](http://i.ytimg.com/vi/xmTIKWJUMPM/mqdefault.jpg)
Please do like & share with your friends or other coding communities, ifff and only if you like our videos & want us to make more such regular editorials. Your motivation to watch these videos is to get high package jobs & my motivation is your love ❤
Bhaiya you are amazing teacher...
Bechara was personal🤣. Thanku pura question ache se samajh aa gya.
One of the best explanation of a hard problem i ever saw. Thanks bro. Keep up the Good work!
Ohhh god when will I be able to solve these problems all by myself. But great explanation
bhayia slides v share krdea kro... helpfull raheta hai... notes bnane mai
The best explanation! was fun to watch how u called the lowest wage person bechara😂
one doubt @ 24:07 Since we're using the ratio of the new quantity, that quantity should be part of the quantitySum.. suppose the heap size > k and the new quantity is the greatest say 5 and we need to remove it.. in that case, what if we remove it from the heap & qualitySum and just use it's ratio?
That is an awesome question, firstly hats off to even think in such deep🫡
.
But my claim is : if quality is high of curRatio that we will have to ultimately remove from priority queue, then it will never contribute to minAns.
.
.
Conclusion: thus including or excluding this ratio will never even matter for our ans
.
.
Proof: Also proof is purely mathematically but i’ll explain with an example ( making this example generic )
.
.
Step1- as all ratios are sorted thus number these ratios as r1, r2, r3, r4. Now as they are sorted just assign them random but sorted values. r1 = 1, r2 = 2, r3 = 3, r4 = 4 (you can take any ratio values but sorted)
Step 2 - now we imagine we had to take 2 employees, and also imagine you are at 4th employee i.e. index = 3 (4th employee)
Step 3 - (Assumption to prove the fact) - Now we are saying the ith employee has higher quality & we already have lesser k qualities in the heap. Okay, lets say ith employee has quality 5, while you already had in the heap quality of 2 & quality of 1 (imagine for index 1 & 2 respectively)
Step 4 - Now as ratios are sorted in ascending order and index3 employee had a ratio of 4 (r4 = 4) and quality as 5 (just considered higher than 2 & 1), so wage which i'll be giving this 3rd index employee will be 5 * 4 = 20$
Step 5 - While if we already had a quality of 2 (taking max quality out of 2 & 1), and we also know its ration will for sure be less than 3rd employee (assumed ratio was 2), thus his wage will be 2*2 = 4 (same will follow for second employee too)
Thus, it proves, that as ratios are sorted in ascending order, this will make sure we take minRatio & multiply by minQualitySum to get minPaidSalary to these k employees.
I hope this solves the doubt.
The simple explanation is that if we removed the person and used his ratio, that means we are using a higher ratio (since sorted) in the current iteration, but using the quality from last iteration. This will never be minimum than the previous ans and won't matter in the end
Honeslty i derive the formula that u derive , but uske baad how to use it i learnt from u👍..this is my learning
Brilliant Aryan.
good luck, coming up with this during interview😮💨
your explanation was really good
it would have been great if you could have dry run a complete example at the end
Nice explanation ❤
Great explanation 🙌
great work brother.. hats off..
best explanation for this problem
Excellent explanation😃😃
Amazing explaination , Didn't imagine I will completely understand hard problem in 1 go.
I know I am asking for lot but can you make a giude on how should I follow your intution building playlists becoz questions are arranged in cronological order and some questions are difficult to understand at first
You explained it very well. Thanks a lot.
Request you to kindly also do LC 759 , 871.
This dialogue holds for this awsome video "aryan bhai ke age koi bol skta hai ky....."
📢🫡📈
Great Explanation!!
@ARYANMITTAL what happen if the i th element got removed from priority queue?
That is an awesome question, firstly hats off to even think in such deep🫡
.
But my claim is : if quality is high of curRatio that we will have to ultimately remove from priority queue, then it will never contribute to minAns.
.
.
Conclusion: thus including or excluding this ratio will never even matter for our ans
.
.
Proof: Also proof is purely mathematically but i’ll explain with an example ( making this example generic )
.
.
Step1- as all ratios are sorted thus number these ratios as r1, r2, r3, r4. Now as they are sorted just assign them random but sorted values. r1 = 1, r2 = 2, r3 = 3, r4 = 4 (you can take any ratio values but sorted)
Step 2 - now we imagine we had to take 2 employees, and also imagine you are at 4th employee i.e. index = 3 (4th employee)
Step 3 - (Assumption to prove the fact) - Now we are saying the ith employee has higher quality & we already have lesser k qualities in the heap. Okay, lets say ith employee has quality 5, while you already had in the heap quality of 2 & quality of 1 (imagine for index 1 & 2 respectively)
Step 4 - Now as ratios are sorted in ascending order and index3 employee had a ratio of 4 (r4 = 4) and quality as 5 (just considered higher than 2 & 1), so wage which i'll be giving this 3rd index employee will be 5 * 4 = 20$
Step 5 - While if we already had a quality of 2 (taking max quality out of 2 & 1), and we also know its ration will for sure be less than 3rd employee (assumed ratio was 2), thus his wage will be 2*2 = 4 (same will follow for second employee too)
Thus, it proves, that as ratios are sorted in ascending order, this will make sure we take minRatio & multiply by minQualitySum to get minPaidSalary to these k employees.
I hope this solves the doubt.
I am constantly learning new things from your videos thats why I am able to think in depth. Thank you for these awesome videos bro and awesome explanation too :)
Great Explanation, Thanks
Amazing 🔥🔥
Great Explanation !
Excellent explanation
Well Explained
i don't get him after 18:00
What should I do when I don't have such an intuition for questions like that ?
Thank you for explanation.
you should share the notes
Can anyone help me with this part?
I get it that we will find the minimum pay by sorting the ratios and maintaining a priority queue to get the min qualities, but what if that total cost that we found didn't meet the minimum wage expectation of one or more people?
We are taking values which are behind the current index and the array is sorted based so for ith element either we will pick its own ratio or a ratio bigger than its ratio which will eventually give more than its min wage
Best explanation
How do you manage to get these questions done during a live contest?
bhaiya jhoot ni bolunga, ekdam sir k uppar se gaya ye question................LEETCODE HARD NI BANTE HAIN MUJHSE😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭
Please share code solution as well
hello ji just search for that video got it in just NOW
Bilkul ji ❤, thank you ji 🫂
i am not getting one thing , In the code how am i making sure that i do not pick someone such that the ratio*quality of that person is lesser than his minimun wage ??
Already explained in video bro, when i told, club both the conditions thus we arrived on our final condition
just for your reach commenting good guy
bro where are we checking that the paid amount is more than minimum wage amount?
same doubt
plz reply if got the answer
first we have taken the ratio(wage/q => wage per quality) stored in vectorworkers (dbl:ratio, int:quality). then sorted workers means for all i
@@jevinmakwana6811 got it in dry run thanks
Since we are sorting by w/q ratio,if we use w/q ratio for a quality values corresponding to higher w/q ratio,we will see that the wage for the person with high w/q ratio will go below his minimum wage value,and so this condition has to be true for every person whose w/q ratio we are looking to check.
@@jevinmakwana6811 Yes
class Solution {
public:
double mincostToHireWorkers(vector& quality, vector& wage, int k) {
vector workers;
int n = quality.size();
for(int i=0; i k){
q_sum -= q.top();
q.pop();
}
if(q.size() == k)
ans = min(ans, worker.first*q_sum);
}
return ans;
}
};
if anyone don't want to share then just click on share button and copy the link, it will trick the algo.
Space should be :
O(n + k)
meri selection ho gyi h?
10:30 life of a IOS user
maqsad 😅
quality* (not quantity)😭
🥲🙈
I was getting confused if quantity was another thing
bhai ise ganda explanation nhi dekha bol zyda rha hai samjha kuch nhi pa rha
bHAI just keep the things simple, don't talk too much.
what is becha..... this.. that....
don't try to include extra unnecessary things.
Great explanation
Great explanation 🔥🔥🤩