C# LeetCode 1792: Maximum Average Pass Ratio - (Medium)

LeetCode 1792: Maximum Average Pass Ratio - (Medium Difficulty)

Intuition

Needed a way to determine which class would yield the best return on adding the extra students.

Best way to track this in my mind would be tracking a Priority, so a PriorityQueue would be ideal for this scenario. A PriorityQueue lets us always select the class with the current highest gain efficiently in O(log n) time per operation.

Approach

• Populate the queue with initial values and the gain in pass ratio from adding one student to each class.

• For each student, take the class with the highest gain from adding one more passing student.

• Loop over the priority queue adding up all the ratios and divide by number of classes to get the average ratio.

Example

Let's say you have two classes:

Class	Pass	Total	Initial Gain from 1 Student
A	1	2	0.1667
B	3	5	0.0667

First assignment:

Class A has higher gain → gets 1 student → now A = [2,3]

Next round:

New gain for A:
(3/4) - (2/3) = 0.75 - 0.6667 = 0.0833

Class B still has gain:
(4/6) - (3/5) = 0.6667 - 0.6 = 0.0667

→ A still has higher gain (0.0833 vs 0.0667), so gets another student.

Now A = [3,4]

Third round:

Gain for A now:
(4/5) - (3/4) = 0.8 - 0.75 = 0.05

Class B gain is still 0.0667

✅ Now B has higher gain — it gets the next student.

When solving this problem, you might wonder:

“Aren’t we already adding one extra student when we calculate the initial gain? Then adding more? Isn’t that overcounting?”

The answer is no — and here’s why.

The iniital gain is just a prediction. When we calculate the gain for a class:

Gain(pass, total) = Ratio(pass + 1, total + 1) - Ratio(pass, total)

We're not actually adding a student.
We're just asking a "what if" question:

“If I gave one extra passing student to this class, how much would its pass ratio improve?”

This helps us prioritize which class would benefit the most if it were chosen next.

Code

public class Solution {
    public double MaxAverageRatio(int[][] classes, int extraStudents)
    {
        var pq = new PriorityQueue<(int pass, int total), double>(
            Comparer<double>.Create((a, b) => b.CompareTo(a))
        );

        // Populate the queue with initial values
        foreach (var cls in classes)
        {
            var pass = cls[0];
            var total = cls[1];
            pq.Enqueue((pass, total), Gain(pass, total));
        }

        // Distribute extra students
        for (var i = 0; i < extraStudents; i++)
        {
            var (pass, total) = pq.Dequeue();
            pass++;
            total++;
            pq.Enqueue((pass, total), Gain(pass, total));
        }

        // After distribution, calculate final average
        double sum = 0;
        while (pq.Count > 0)
        {
            var (pass, total) = pq.Dequeue();
            sum += CalculateRatio(pass, total);
        }

        return sum / classes.Length;
    }

    double CalculateRatio(int pass, int total)
    {
        return (double)pass / total;
    }

    double Gain(int pass, int total)
    {
        var current = CalculateRatio(pass, total);
        var after = CalculateRatio(pass + 1, total + 1);
        return after - current;
    }
}