Maximum Average Pass Ratio | Leetcode 1792

[@somnathchoudhury321]

Great explanation sir

[@techdose4u]

thanks :)

[@MAHALAKSHMIVEERARAJ]

Thank you so much for the great explanation!

[@techdose4u]

welcome :)

[@Ajithkumar-gt2rx]

4:42 Small correction that the brute force solution is not n ^ n but actually it is n *n

[@techdose4u]

I will try all possibillities using the N-ary type recursion solution :)
Maybe I came up with something worse than existing bruteforce :|
In this, we are blindly assigning without choosing best possibility.
If you choose best option using linear search then it will be N^2, which is optimized to NlogN using Maxheap

[@sailendrachettri8521]

Thank you sir :)

[@techdose4u]

Welcome :)

[@malindailankoon]

why do we consider the increment instead of new pass ratio for each class? can there be a situation such that for a certain class the increment is higher when adding a student but the new pass ratio is less compared to some other class?

[@techdose4u]

I think I have shown a case where it doesnt work if you consider greedy on least avg and works well if you take Possible increment.
You can consider solving two city scheduling to get more clarity :)

[@adityasehdev514]

Great video

[@techdose4u]

Thanks :)

[@NitishKumar-vi7sq]

I've one doubt. When you are adding pushing the classes in heap in for loop. Why you are adding an extra student there when calculating new avg? What is the idea? Didn't get you there.

[@beinghappy9223]

Thank you so much for the awesome explanation . Here is my code based on your explanation :
class Solution {
public:
//TC : O((extrastudents+n)*logn)
//SC : O(n)
typedef pair pr;
double calculateIncrement(int pass, int total){
double curr_avg = (double)pass/total;
double new_avg = (double)(pass+1)/(total+1);
double increment = new_avg - curr_avg;
return increment;
}
double maxAverageRatio(vector& classes, int extraStudents) {
//greedy possible increment : maxHeap
int n = classes.size();
priority_queuepq;
for(int i=0;i