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.
This approach optimizes the greedy strategy by using a max-heap (Priority Queue). Instead of repeatedly scanning all classes to find the one with the maximum potential ratio increase, we store all classes in a max-heap prioritized by this increase. This allows us to find the best class in logarithmic time instead of linear time, making the solution efficient enough for the given constraints.
Algorithm
- Initialize a max-heap (like Java's
PriorityQueuewith a custom comparator) to store class information, prioritized by the potential ratio increase. - For each class
c = [pass, total]in the input:- Calculate the initial ratio increase
delta = (total - pass) / (total * (total + 1)). - Add an object or array representing the class, like
{delta, pass, total}, to the max-heap.
- Calculate the initial ratio increase
- Loop
extraStudentstimes:- Extract the element with the maximum
deltafrom the heap. This represents the class that gives the best improvement. - Update its counts:
new_pass = pass + 1,new_total = total + 1. - Recalculate the
new_deltafor this updated class. - Add the updated class information back to the heap.
- Extract the element with the maximum
- After the loop, the heap contains the final configurations of all classes.
- Initialize
total_ratio_sum = 0. - While the heap is not empty, extract each class, calculate its ratio
pass / total, and add it tototal_ratio_sum. - Return
total_ratio_sum / number of classes.
Walkthrough
The key observation is that the brute-force approach is slow because of the repeated search for the maximum increase. A max-heap is the ideal data structure to efficiently retrieve the maximum element at each step.
We define the "priority" of a class as the gain in pass ratio we get by adding one extra student. This gain, delta, is calculated as (p + 1) / (t + 1) - p / t, which simplifies to the more numerically stable formula (t - p) / (t * (t + 1)). By storing classes in a max-heap ordered by this delta, we can always access the most beneficial class to update in O(log n) time.
import java.util.PriorityQueue; class Solution { public double maxAverageRatio(int[][] classes, int extraStudents) { int n = classes.length; // Max-heap to store classes, ordered by the potential increase in pass ratio. // The element is a double array: {increase, pass, total} PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0])); for (int[] c : classes) { double pass = c[0]; double total = c[1]; // The increase is (t - p) / (t * (t + 1)) double increase = (total - pass) / (total * (total + 1)); pq.offer(new double[]{increase, pass, total}); } // Distribute the extra students for (int i = 0; i < extraStudents; i++) { double[] current = pq.poll(); double pass = current[1] + 1; double total = current[2] + 1; // Calculate the new potential increase for this class double newIncrease = (total - pass) / (total * (total + 1)); pq.offer(new double[]{newIncrease, pass, total}); } // Calculate the total average ratio double totalRatioSum = 0; while (!pq.isEmpty()) { double[] c = pq.poll(); totalRatioSum += c[1] / c[2]; } return totalRatioSum / n; }}Complexity
Time
O((n + k) * log n), where `k` is `extraStudents` and `n` is `classes.length`. Building the heap takes `O(n * log n)`. Then, for each of the `k` students, we perform one poll and one offer operation, each taking `O(log n)` time.
Space
O(n), to store all `n` classes in the max-heap.
Trade-offs
Pros
Highly efficient, passing all test cases within the time limit.
Optimal greedy approach for this problem.
Cons
More complex to implement than the brute-force approach due to the use of a heap.
Requires extra space for the heap.
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; }}class Solution {public: double maxAverageRatio(vector<vector<int>> &classes, int extraStudents) { priority_queue<tuple<double, int, int>> pq; for (auto &e : classes) { int a = e[0], b = e[1]; double x = (double)(a + 1) / (b + 1) - (double)a / b; pq.push({x, a, b}); } while (extraStudents--) { auto [_, a, b] = pq.top(); pq.pop(); a++; b++; double x = (double)(a + 1) / (b + 1) - (double)a / b; pq.push({x, a, b}); } double ans = 0; while (pq.size()) { auto [_, a, b] = pq.top(); pq.pop(); ans += (double)a / b; } return ans / classes.size(); }};class Solution: def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float: h = [(a / b - (a + 1) / (b + 1), a, b) for a, b in classes] heapify(h) for _ in range(extraStudents): _, a, b = heappop(h) a, b = a + 1, b + 1 heappush(h, (a / b - (a + 1) / (b + 1), a, b)) return sum(v[1] / v[2] for v in h) / len(classes)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.