Maximum Average Pass Ratio
MedPrompt
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:
extraStudentsExample 2:
extraStudents
Constraints:
1 <= classes.length <= 105classes[i].length == 21 <= passi <= totali <= 1051 <= extraStudents <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
This approach simulates the process directly. For each of the extraStudents, it iterates through all the classes to find the one that would yield the highest increase in pass ratio if the student were added to it. After finding the best class, it updates that class's student counts and repeats the process for the next student.
Algorithm
- Create a mutable copy of the
classesarray, usingdoubleto maintain precision. - Loop
extraStudentstimes. - In each iteration of the loop, find the best class to update:
- Initialize
maxIncreaseto a very small number andbestClassIndexto -1. - Iterate through all classes. For each class, calculate the potential increase in its pass ratio if one student is added. The increase is
(pass + 1) / (total + 1) - pass / total. - If this increase is greater than
maxIncrease, updatemaxIncreaseandbestClassIndex.
- Initialize
- After scanning all classes, add one student to the class at
bestClassIndexby incrementing its pass and total counts. - After the main loop finishes, calculate the sum of the final pass ratios of all classes.
- Return the sum divided by the total number of classes.
Walkthrough
The core idea is a greedy one: at each step, make the locally optimal choice. The best choice for placing one student is to add them to the class where the gain in the pass ratio is maximized. This approach implements this greedy strategy in the most straightforward way, by repeatedly searching for the best class to augment.
class Solution { public double maxAverageRatio(int[][] classes, int extraStudents) { int n = classes.length; // Create a copy to modify, using doubles for precision double[][] currentClasses = new double[n][2]; for (int i = 0; i < n; i++) { currentClasses[i][0] = classes[i][0]; currentClasses[i][1] = classes[i][1]; } // Distribute each extra student one by one for (int i = 0; i < extraStudents; i++) { int bestClassIndex = -1; double maxIncrease = -1.0; // Find the class that gives the maximum increase in ratio for (int j = 0; j < n; j++) { double pass = currentClasses[j][0]; double total = currentClasses[j][1]; // Calculate the increase in ratio if one student is added. double increase = (pass + 1) / (total + 1) - pass / total; if (increase > maxIncrease) { maxIncrease = increase; bestClassIndex = j; } } // Add the student to the best class found if (bestClassIndex != -1) { currentClasses[bestClassIndex][0]++; currentClasses[bestClassIndex][1]++; } } // Calculate the final average ratio double totalRatioSum = 0; for (int i = 0; i < n; i++) { totalRatioSum += currentClasses[i][0] / currentClasses[i][1]; } return totalRatioSum / n; }}Complexity
Time
O(k * n), where `k` is `extraStudents` and `n` is `classes.length`. For each of the `k` students, we perform a linear scan of `n` classes to find the best one to update.
Space
O(n), where `n` is the number of classes. This is for storing a mutable copy of the classes data. If the input array is modified in-place, the space complexity would be O(1).
Trade-offs
Pros
Simple to understand and implement.
Correctly follows the greedy logic without complex data structures.
Cons
Highly inefficient due to the repeated linear scan of all classes for each extra student.
Will result in a "Time Limit Exceeded" error on platforms like LeetCode for the given constraints.
Solutions
Solution
class Solution {public double maxAverageRatio(int[][] classes, int extraStudents) { PriorityQueue<double[]> pq = new PriorityQueue<>((a, b)->{ double x = (a[0] + 1) / (a[1] + 1) - a[0] / a[1]; double y = (b[0] + 1) / (b[1] + 1) - b[0] / b[1]; return Double.compare(y, x); }); for (var e : classes) { pq.offer(new double[]{e[0], e[1]}); } while (extraStudents-- > 0) { var e = pq.poll(); double a = e[0] + 1, b = e[1] + 1; pq.offer(new double[]{a, b}); } double ans = 0; while (!pq.isEmpty()) { var e = pq.poll(); ans += e[0] / e[1]; } return ans / classes.length; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.