Intuition building from brute to optimal approach. T.C --> O(extraStudents x logn)
ApproachInitially, tried solving this question using a greedy approach by adding 1 extra student to the class having the smallest pass-ratio, which is students/
# Approach\n\nInitially, tried solving this question using a greedy approach by adding 1 extra student to the class having the smallest pass-ratio, which is students/totalNoOfStudents in a class, and repeating the same process till there exists extraStudents.\n\nBut, this approach fails in the very first example given here on Leetcode.\n\nTherefore, correct approach for this problem is to consider the difference between the new pass ratio by adding 1 extra student to a class & current pass ratio (existing pass-ratio).\n\nSolutions, given here is based on considering the delta/difference between the new pass ratio & existing pass ratio.\n\n# Complexity\n- Time complexity:\nFor 1st solution -> O(2n) + O(extraStudents x n) == O(n + (extraStudents x n))\n\nFor 2nd (Optimal) solution -> O(nlogn) + O(extraStudents x logn) + O(n) == O(nlogn + (extraStudents x logn) + n)\n\n- Space complexity:\nFor both solutions -> O(n)\n\n# Code\nKind of brute force based on difference of pass ratios. Gives TLE\n```cpp []\nclass Solution {\npublic:\n    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {\n        \n        int n = classes.size();     //T.C --> O(2n) + O(extraStudents x n)   ||   S.C --> O(n)\n\n        vector<double> pass_ratio(n);\n\n        for(int i=0; i<n; i++) {        //O(n)\n\n            double pr = (classes[i][0] * 1.0)/classes[i][1];\n\n            pass_ratio[i] = pr;\n        }\n\n        while(extraStudents--) {        //O(extraStudents x n)\n\n            double maxNewPR = INT_MIN, maxNewPRDiff = INT_MIN;\n\n            int idx = 0;\n\n            for(int i=0; i<n; i++) {\n\n                double newPR = ((classes[i][0] + 1) * 1.0)/(classes[i][1] + 1);\n\n                double diff = newPR - pass_ratio[i];\n\n                if(diff > maxNewPRDiff) {\n\n                    maxNewPR = newPR;\n\n                    maxNewPRDiff = diff;\n\n                    idx = i;\n                }\n            }\n\n            pass_ratio[idx] = maxNewPR;\n\n            classes[idx][0]++;\n            classes[idx][1]++;\n        }\n\n        double sum = 0;\n\n        for(auto &it : pass_ratio)      //O(n)\n            sum += it;\n        \n        double avg = (sum * 1.0) / n;\n\n        return avg;\n    }\n};\n\n\n```\n\nOptimal Approach using max heap.\n```cpp []\n#define pdd pair<double, double>\n\nclass Solution {\npublic:\n    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {\n        \n        int n = classes.size(); //T.C --> O(nlogn + (extraStudents x logn) + n)  ||  S.C --> O(n)\n\n        priority_queue<pdd> maxHeap;    //{delta, idx}\n\n        //O(nlogn)\n        for(int i=0; i<n; i++) {    //Pre-processing for 1 extra student allotted to every class\n\n            double pr = (classes[i][0] * 1.0)/classes[i][1];\n\n            double newPR = ((classes[i][0] + 1) * 1.0)/(classes[i][1] + 1);\n\n            double delta = newPR - pr;\n\n            maxHeap.push({delta, i});\n        }\n\n        while(extraStudents--) {    //O(extraStudents x log(n))\n\n            auto curr = maxHeap.top();\n            maxHeap.pop();      //log(n)\n\n            double delta = curr.first;\n            int idx = curr.second;\n\n            //Updating the classes for max delta idx\n            classes[idx][0]++;\n            classes[idx][1]++;\n\n            //Now adding 1 extra student to idx and pushing new delta to max heap\n            double currPRForIdx = (classes[idx][0] * 1.0)/classes[idx][1];\n\n            double newPRForIdx = ((classes[idx][0] + 1) * 1.0)/(classes[idx][1] + 1);   //After adding 1 extra student\n\n            double newDelta = newPRForIdx - currPRForIdx;\n\n            maxHeap.push({newDelta, idx});      //log(n)\n        }\n\n        double sum = 0;\n\n        for(int i=0; i<n; i++) {        //O(n)\n\n            double pr = (classes[i][0] * 1.0)/classes[i][1];\n\n            sum += pr;\n        }\n            \n        double avg = (sum * 1.0) / n;\n\n        return avg;\n    }\n};\n```
['Array', 'Greedy', 'Heap (Priority Queue)', 'C++']