Watch 10 video solutions for Maximum Average Pass Ratio, a medium level problem involving Array, Greedy, Heap (Priority Queue). This walkthrough by codestorywithMIK has 14,937 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There is a school that has classes of students and each class will be having a final exam. You are given a 2D integer array classes, where classes[i] = [passi, totali]. You know beforehand that in the ith class, there are totali total students, but only passi number of students will pass the exam.
You are also given an integer extraStudents. There are another extraStudents brilliant students that are guaranteed to pass the exam of any class they are assigned to. You want to assign each of the extraStudents students to a class in a way that maximizes the average pass ratio across all the classes.
The pass ratio of a class is equal to the number of students of the class that will pass the exam divided by the total number of students of the class. The average pass ratio is the sum of pass ratios of all the classes divided by the number of the classes.
Return the maximum possible average pass ratio after assigning the extraStudents students. Answers within 10-5 of the actual answer will be accepted.
Example 1:
Input: classes = [[1,2],[3,5],[2,2]], extraStudents = 2
Output: 0.78333
Explanation: You can assign the two extra students to the first class. The average pass ratio will be equal to (3/4 + 3/5 + 2/2) / 3 = 0.78333.
Example 2:
Input: classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
Output: 0.53485
Constraints:
1 <= classes.length <= 105classes[i].length == 21 <= passi <= totali <= 1051 <= extraStudents <= 105Problem Overview: You are given several classes where pass[i] students out of total[i] passed. Extra students are guaranteed to pass their class. The goal is to assign these extra students across classes to maximize the overall average pass ratio.
Approach 1: Greedy + Priority Queue (O((n + k) log n) time, O(n) space)
The key observation: adding a student to different classes increases the pass ratio by different amounts. The gain from assigning one student to a class is (p+1)/(t+1) - p/t. Always assign the next student to the class with the largest improvement. This greedy choice ensures each step maximizes the global average increase.
Use a max heap (Heap (Priority Queue)) where each entry stores the improvement value and the class state (pass, total). Initialize the heap with all classes. Repeatedly pop the class with the highest gain, update its values after adding a student, recompute the gain, and push it back into the heap. After distributing all extra students, compute the final average pass ratio across all classes. Heap operations take O(log n), giving overall complexity O((n + k) log n).
This solution combines Greedy decision making with a Priority Queue to efficiently pick the best class each time. It scales well even when the number of extra students is large.
Approach 2: Direct Simulation (O(n * k) time, O(1) extra space)
A straightforward strategy repeatedly checks every class to determine which one benefits the most from receiving the next student. For each extra student, iterate through the entire Array of classes, compute the improvement for each class, and pick the maximum. Then update that class and continue.
This approach is easy to implement because it avoids advanced data structures. However, each allocation requires scanning all n classes. With k extra students, the total runtime becomes O(n * k), which becomes slow when both values are large.
Recommended for interviews: The greedy priority queue solution is the expected approach. It shows you can quantify marginal gain and maintain the best candidate efficiently with a heap. Discussing the direct simulation first demonstrates baseline reasoning, but implementing the heap-based greedy approach proves strong algorithmic and data structure skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy + Priority Queue | O((n + k) log n) | O(n) | General case. Efficient when many extra students must be distributed. |
| Direct Simulation | O(n * k) | O(1) | Small inputs or when avoiding heap implementation. |