857. Minimum Cost to Hire K Workers | Priority Queue | Heap | Kinda Sliding Window

In this video, I'll talk about how to solve Leetcode 857. Minimum Cost to Hire K Workers | Priority Queue | Heap | Kinda Sliding Window
Let's Connect:
📱Discord (Join Community) : / discord
📝Linkedin: / aryan-mittal-0077
📸 Instagram: / codewitharyanbhai
💻 Twitter - / aryan_mittal007
🤖 Github: github.com/aryan-0077
About Me:
I am Aryan Mittal - A Software Engineer in Goldman Sachs, Speaker, Creator & Educator. During my free time, I create programming education content on this channel & also how to use that to grow :)
✨ Hashtags ✨
#programming #Interviews #leetcode #faang #maang #datastructures #algorithms

[@ARYANMITTAL]

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 ❤

[@anurag_vish]

Bhaiya you are amazing teacher...

[@shivchauhan795]

Bechara was personal🤣. Thanku pura question ache se samajh aa gya.

[@mrityunjoybarman9098]

Ohhh god when will I be able to solve these problems all by myself. But great explanation

[@shikharchaturvedi5093]

One of the best explanation of a hard problem i ever saw. Thanks bro. Keep up the Good work!

[@lavanyam3224]

The best explanation! was fun to watch how u called the lowest wage person bechara😂

[@lavanyam3224]

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?

[@ARYANMITTAL]

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.

[@abhimanyuambastha2595]

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

[@gursimransingh3707]

bhayia slides v share krdea kro... helpfull raheta hai... notes bnane mai

[@ushapandey1088]

Honeslty i derive the formula that u derive , but uske baad how to use it i learnt from u👍..this is my learning

[@kandariarjun]

You explained it very well. Thanks a lot.

[@vishwakarma-gaurav]

Amazing 🔥🔥

[@IK-xk7ex]

Thank you for explanation.

[@prathameshautade2679]

Great Explanation, Thanks

[@chinmoydebnath353]

good luck, coming up with this during interview😮‍💨

[@dhineshd94]

best explanation for this problem

[@rajrajesh1669]

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?

[@manoharmanu9240]

Great explanation 🙌

[@akshayawasthi599]

great work brother.. hats off..

[@piyushsingh9320]

Great Explanation !

[@prathamjain8937]

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

[@ShivamYadav-vg5fv]

How do you manage to get these questions done during a live contest?

[@iamnoob7593]

Brilliant Aryan.

[@navinbarnwal4782]

Nice explanation ❤

[@abiraljain7313]

Great explanation 🔥🔥🤩

[@yuvikasingh9635]

Excellent explanation

[@HIMANSHUYADAV-dt2kb]

Excellent explanation😃😃

[@avinashkumar8147]

Best explanation

[@parthgupta971]

@ARYANMITTAL what happen if the i th element got removed from priority queue?

[@ARYANMITTAL]

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.

[@parthgupta971]

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

[@cenacr007]

Well Explained

[@MichaBalcerak]

What should I do when I don't have such an intuition for questions like that ?

[@floatingpoint7629]

your explanation was really good

[@floatingpoint7629]

it would have been great if you could have dry run a complete example at the end

[@iamnoob7593]

Request you to kindly also do LC 759 , 871.

[@Anushka20037]

i don't get him after 18:00

[@kartikeyasingh5172]

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 ??

[@ARYANMITTAL]

Already explained in video bro, when i told, club both the conditions thus we arrived on our final condition

[@ompatel2212]

you should share the notes

[@mukulkhanna5071]

This dialogue holds for this awsome video "aryan bhai ke age koi bol skta hai ky....."

[@ARYANMITTAL]

📢🫡📈

[@prashantsahu5117]

hello ji just search for that video got it in just NOW

[@ARYANMITTAL]

Bilkul ji ❤, thank you ji 🫂

[@tanyaraj3129]

just for your reach commenting good guy

[@kratimishra2283]

Please share code solution as well

[@nikeshmali8506]

if anyone don't want to share then just click on share button and copy the link, it will trick the algo.

[@AmanChandna-bv4tt]

meri selection ho gyi h?

[@asmitshukla4649]

bhaiya jhoot ni bolunga, ekdam sir k uppar se gaya ye question................LEETCODE HARD NI BANTE HAIN MUJHSE😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭

[@AnujGupta-xi5ep]

Space should be : O(n + k)

[@jevinmakwana6811]

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; } };

[@siddheshpatil5995]

bro where are we checking that the paid amount is more than minimum wage amount?

[@nooob_coder]

same doubt plz reply if got the answer

[@jevinmakwana6811]

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

[@nooob_coder]

@@jevinmakwana6811 got it in dry run thanks

[@petermj2804]

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.

[@chaitanyaamajala2582]

@@jevinmakwana6811 Yes

[@brp3522]

10:30 life of a IOS user

[@aloksachan8572]

maqsad 😅

[@daveloperkrishana7559]

quality* (not quantity)😭

[@ARYANMITTAL]

🥲🙈

[@sangdilbiswal30]

I was getting confused if quantity was another thing

[@YashAgarwal-tf2rl]

bhai ise ganda explanation nhi dekha bol zyda rha hai samjha kuch nhi pa rha

[@praveensingh5729]

bHAI just keep the things simple, don't talk too much. what is becha..... this.. that.... don't try to include extra unnecessary things.

[@Engineering.Wallah]

Great explanation

[@ShristiSethiya-ch2he]

Great Explanation!!