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.
This approach uses a priority queue (or max heap) to determine which class will benefit the most from an extra student in terms of maximizing the pass ratio. The difference in pass ratio by adding an extra student is calculated for each class, and at each step, the student is added to the class with the maximum benefit.
Initially, calculate the potential pass ratio increase for one extra student to each class, insert these into the priority queue. Pop from the queue to get the class with maximum potential increase, add an extra student, calculate the new potential increase, and push it back to the queue. Repeat until all extra students are allocated.
The code utilizes a max heap to always pop the class that gains the most from an extra student. Each class's gain is defined as the change in pass ratio if an extra student is added. After processing all extra students, the average pass ratio is calculated and returned.
Time Complexity: O((n + extraStudents) log n) where n is the number of classes.
Space Complexity: O(n) for storing classes in the heap.
This approach directly simulates the process of assigning extra students by iterating over each class and finding the gain for each possible allocation of extra students. Though less efficient, this is simpler and works within constraints when the number of classes or extra students is small.
The solution maintains a priority queue of class information using a custom comparator to prioritize classes that benefit the most from additional students. Each time a student is assigned, the ratios are recalculated.
Java
JavaScript
Time Complexity: O((n + E) * log n), where E is the number of extraStudents.
Space Complexity: O(n) for storing ratios in the priority queue.
Suppose a class currently has a pass rate of \frac{a}{b}. If we arrange a smart student into this class, then the pass rate of the class will become \frac{a+1}{b+1}. We can find that the increment of the pass rate is \frac{a+1}{b+1} - \frac{a}{b}.
We maintain a max-heap, which stores the increment of the pass rate for each class.
Perform extraStudents operations, each time taking a class from the top of the heap, adding 1 to both the number of students and the number of passes in this class, then recalculating the increment of the pass rate of this class and putting it back into the heap. Repeat this process until all students are allocated.
Finally, we sum up the pass rates of all classes, and then divide by the number of classes to get the answer.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of classes.
| Approach | Complexity |
|---|---|
| Approach 1: Greedy + Priority Queue | Time Complexity: O((n + extraStudents) log n) where n is the number of classes. Space Complexity: O(n) for storing classes in the heap. |
| Approach 2: Direct Simulation | Time Complexity: O((n + E) * log n), where E is the number of extraStudents. Space Complexity: O(n) for storing ratios in the priority queue. |
| Priority Queue (Max-Heap of Increment) | — |
| 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. |
Maximum Average Pass Ratio | Detailed | Covered Minute Details | Leetcode 1792 | codestorywithMIK • codestorywithMIK • 14,937 views views
Watch 9 more video solutions →Practice Maximum Average Pass Ratio with our built-in code editor and test cases.
Practice on FleetCode