Why this fails

The time complexity of this approach is $O(K \cdot N)$, where $K$ is the number of extra students and $N$ is the number of classes. Given the constraints $N, K \le 10^5$, the total operations could reach $10^{10}$, which will inevitably result in a Time Limit Exceeded (TLE) error. We need a way to find the maximum gain without scanning the entire list every time.

Core Insight for Maximum Average Pass Ratio

The key intuition is to define the benefit of assigning a student mathematically. We define the profit or gain of adding a student to a specific class as the change in its pass ratio:

$\Delta(p, t) = \frac{p+1}{t+1} - \frac{p}{t}$

Where $p$ is the number of passing students and $t$ is the total students.

We want to maximize the total sum of ratios. Since the "gain" from adding a student diminishes as the class size grows (diminishing returns), we must pick the class with the highest current $\Delta$ for every single extra student we assign.

Instead of scanning all classes to find the max $\Delta$ (which is $O(N)$), we can maintain the classes in a Max-Heap (Priority Queue). The heap orders the classes based on their potential gain. This allows us to retrieve the best candidate in $O(1)$ time and update the structure in $O(\log N)$ time after assigning a student.

Visual Description: Imagine a Priority Queue as a tiered structure where the class that would improve the most sits at the very top.

1. We peek at the top node; this is the class that gives the highest ratio boost right now.
2. We "assign" a student to this class (conceptually updating its pass/total counts).
3. The class's potential for future improvement drops (due to diminishing returns), so it sinks lower into the heap to its new correct position.
4. The next best candidate bubbles up to the top for the next student assignment.

Execution Flow

Let's trace the algorithm with classes = [[1,2], [3,5], [2,2]] and extraStudents = 2.

1. Initialization:

   • Class A [1,2]: Ratio 0.5. New Ratio if added: $2/3 \approx 0.666$. Gain: $0.166$.
   • Class B [3,5]: Ratio 0.6. New Ratio if added: $4/6 \approx 0.666$. Gain: $0.066$.
   • Class C [2,2]: Ratio 1.0. New Ratio if added: $3/3 = 1.0$. Gain: $0.0$.
   • Heap: [(0.166, 1, 2), (0.066, 3, 5), (0.0, 2, 2)].

2. Student 1 Assignment:

   • Pop max: Class A [1,2] with gain $0.166$.
   • Update Class A: 1 -> 2 pass, 2 -> 3 total.
   • New Gain for A: $\frac{3}{4} - \frac{2}{3} = 0.75 - 0.666 = 0.0833$.

3. Student 2 Assignment:

   • Pop max: Class A [2,3] with gain $0.0833$.
   • Update Class A: 2 -> 3 pass, 3 -> 4 total.
   • New Gain for A: $\frac{4}{5} - \frac{3}{4} = 0.8 - 0.75 = 0.05$.

4. Final Calculation:

   • Sum ratios:
     • Class B: $3/5 = 0.6$
     • Class A: $3/4 = 0.75$
     • Class C: $2/2 = 1.0$

Proof of Correctness

The correctness relies on the "Greedy Choice Property." We want to maximize $\sum \frac{p_i}{t_i}$. Since the total number of students to add is fixed, and the contribution of each addition is independent of others except for the class it modifies, we essentially have a sequence of independent choices.

The function describing the gain, $g(p, t) = \frac{p+1}{t+1} - \frac{p}{t}$, is strictly decreasing as $t$ increases (diminishing returns). Adding a student to a class now does not prevent us from adding another student to the same class later; it simply reduces the value of that subsequent addition. Therefore, choosing the local maximum gain at each step guarantees the global maximum sum of ratios.

Reference Implementation

C++ Solution for LeetCode 1792

cpp
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        // Priority queue to store {gain, pass, total}
        // Ordered by gain descending
        priority_queue<pair<double, pair<int, int>>> maxHeap;

        auto calculateGain = [](int pass, int total) {
            return (double)(pass + 1) / (total + 1) - (double)pass / total;
        };

        // Initialize heap
        for (const auto& c : classes) {
            int pass = c[0];
            int total = c[1];
            maxHeap.push({calculateGain(pass, total), {pass, total}});
        }

        // Distribute extra students
        while (extraStudents > 0) {
            auto top = maxHeap.top();
            maxHeap.pop();

            double currentGain = top.first;
            int pass = top.second.first;
            int total = top.second.second;

            // Update the class
            pass++;
            total++;
            extraStudents--;

            // Push back with new gain
            maxHeap.push({calculateGain(pass, total), {pass, total}});
        }

        // Calculate final average
        double totalRatio = 0.0;
        while (!maxHeap.empty()) {
            auto top = maxHeap.top();
            maxHeap.pop();
            totalRatio += (double)top.second.first / top.second.second;
        }

        return totalRatio / classes.size();
    }
};

Java Solution for LeetCode 1792

java
import java.util.PriorityQueue;

class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        // PriorityQueue stores arrays: [gain, pass, total]
        // We use a custom comparator to simulate a Max-Heap based on gain
        PriorityQueue<double[]> maxHeap = new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0]));

        for (int[] c : classes) {
            double pass = c[0];
            double total = c[1];
            double gain = (pass + 1) / (total + 1) - (pass / total);
            maxHeap.offer(new double[]{gain, pass, total});
        }

        while (extraStudents > 0) {
            double[] top = maxHeap.poll();
            double pass = top[1];
            double total = top[2];

            // Add student
            pass++;
            total++;
            extraStudents--;

            // Recalculate gain and push back
            double newGain = (pass + 1) / (total + 1) - (pass / total);
            maxHeap.offer(new double[]{newGain, pass, total});
        }

        double totalRatio = 0.0;
        while (!maxHeap.isEmpty()) {
            double[] top = maxHeap.poll();
            totalRatio += top[1] / top[2];
        }

        return totalRatio / classes.length;
    }
}

Python Solution for LeetCode 1792

python
import heapq

class Solution:
    def maxAverageRatio(self, classes: list[list[int]], extraStudents: int) -> float:
        # Helper to calculate gain
        def calculate_gain(p, t):
            return (p + 1) / (t + 1) - p / t

        # Python's heapq is a min-heap. We store negative gain to simulate max-heap.
        # Structure: (-gain, pass, total)
        heap = []
        for p, t in classes:
            gain = calculate_gain(p, t)
            heapq.heappush(heap, (-gain, p, t))

        # Assign students
        for _ in range(extraStudents):
            neg_gain, p, t = heapq.heappop(heap)
            
            # Update class
            p += 1
            t += 1
            
            # Recalculate and push
            new_gain = calculate_gain(p, t)
            heapq.heappush(heap, (-new_gain, p, t))

        # Calculate final average
        total_ratio = 0
        for _, p, t in heap:
            total_ratio += p / t
            
        return total_ratio / len(classes)

Why can't I just pick the class with the lowest current ratio?

Mistake: Assuming the class with the lowest pass ratio (e.g., 1/100 vs 1/2) will always provide the biggest boost. Reasoning: The "gain" depends on the magnitude of the numbers, not just the ratio. Adding 1 student to 1/2 (0.5) makes it 2/3 (0.66), a gain of ~0.16. Adding 1 student to 1/100 (0.01) makes it 2/101 (0.019), a gain of only ~0.009. Consequence: Your greedy choice will be suboptimal, leading to an incorrect answer.

Why do I need to use floating-point division?

Mistake: Using integer division (e.g., pass / total in C++ or Java) results in 0 or 1, losing all precision. Reasoning: Pass ratios are fractional values between 0 and 1. Integer arithmetic truncates these decimals. Consequence: The logic will treat different ratios as identical (likely 0), breaking the heap ordering and final calculation.

Why do I need to recalculate gain after every assignment?

Mistake: Calculating gains once, sorting, and dumping all students into the top class until it's no longer the best. Reasoning: The gain is dynamic. As soon as you add one student to a class, its denominator increases, significantly reducing the gain from the next student added to that same class. The "best" class changes constantly. Consequence: You fail to re-evaluate the greedy choice, leading to a suboptimal distribution.