Maximum Average Pass Ratio: Greedy Heap Pattern

You are given n classes, where the i-th class has pass[i] students who will pass out of total[i] total students. You also have extraStudents extra brilliant students who are guaranteed to pass any class they are assigned to. Your goal is to assign these extra students to classes in a way that maximizes the average pass ratio across all classes.

This is LeetCode 1792: Maximum Average Pass Ratio.

Why this problem matters

This problem is a textbook example of the greedy + heap pattern. You have a limited resource (extra students) and you need to distribute it optimally. The key question is: which class benefits the most from the next student? If you can answer that question efficiently, you can repeat the process for every student and get the optimal assignment.

The pattern shows up in many real-world optimization problems. Any time you are distributing a finite resource across competing options and want to maximize total benefit, you are looking at a greedy allocation problem. The heap gives you the data structure to always pick the best option in O(log n) time.

What makes this problem particularly clean is that the greedy choice is provably optimal. Assigning each student to the class with the highest marginal gain always leads to the globally best answer. There is no need for dynamic programming or backtracking.

The key insight

When you add one student to a class with ratio pass/total, the new ratio becomes (pass+1)/(total+1). The marginal gain of that assignment is (pass+1)/(total+1) - pass/total. This gain depends on the current values of pass and total, and it changes every time you assign a student to that class.

A max heap lets you always pick the class with the largest marginal gain. You pop the top of the heap, assign a student to that class, recompute its gain with the updated pass and total, and push it back. After all students have been assigned, you compute the average.

The reason this greedy approach works is that the gain function is strictly decreasing for any given class. Each additional student you add to the same class produces a smaller improvement than the previous one. This means it never makes sense to "save" a student for later; you should always give the next student to whoever benefits the most right now.

The solution

import heapq

def max_average_ratio(classes: list[list[int]], extra_students: int) -> float:
    def gain(p, t):
        return (p + 1) / (t + 1) - p / t

    heap = [(-gain(p, t), p, t) for p, t in classes]
    heapq.heapify(heap)

    for _ in range(extra_students):
        _, p, t = heapq.heappop(heap)
        p += 1
        t += 1
        heapq.heappush(heap, (-gain(p, t), p, t))

    return sum((p / t) for _, p, t in heap) / len(heap)

The gain function computes the marginal improvement of adding one student to a class with p passes out of t total. This is the value we use to decide which class gets the next student.

We build the heap by computing the gain for every class and storing it as a tuple (-gain, pass, total). The negation is important because Python's heapq is a min heap. By negating the gain, the class with the largest gain ends up at the top.

The main loop runs once per extra student. Each iteration pops the class with the highest gain, increments both its pass count and total count (the new student passes), recomputes the gain with the updated values, and pushes the class back into the heap.

After all students are assigned, we iterate through the heap and compute the average of all pass ratios.

Visual walkthrough

Let's trace through the example with classes = [[1,2],[3,5],[2,6]] and extraStudents = 2. At each step, we pick the class with the highest marginal gain and assign one student to it.

Notice how after each assignment, the gains shift. Class 3 had the highest gain initially, but after receiving one student, its gain dropped below that of Class 1. The heap always surfaces the current best choice.

Complexity analysis

Time is O((n + k) log n), where n is the number of classes and k is the number of extra students. Building the initial heap takes O(n). Each of the k iterations does one pop and one push, each costing O(log n). The final sum is O(n). So the total is O(n + k log n).

Space is O(n) for the heap, which stores one entry per class.

The building blocks

1. Marginal gain calculation

The core of this problem is computing how much a class improves when it receives one additional passing student:

def gain(p, t):
    return (p + 1) / (t + 1) - p / t

This formula captures the diminishing returns property. A class with a low pass ratio improves more from one extra student than a class that already has a high ratio. Algebraically, the gain simplifies to (t - p) / (t * (t + 1)), which makes it clear that the gain depends on the gap between total and passing students, scaled by the class size.

2. Max heap for greedy selection

The heap ensures that picking the best class at each step costs O(log n) instead of O(n). Without the heap, you would scan all classes for every student, giving O(n * k) total time. With the heap, you get O(k log n), which is much better when k is large.

The pattern is: push all candidates with their priority into a heap, repeatedly extract the best, update it, and push it back. You will see this exact structure in problems like "Reorganize String," "Task Scheduler," and any problem where you repeatedly pick the highest-priority item from a changing set.

Edge cases

• All classes already have 100% pass ratio: every class has pass == total. The gain for every class is 0. The extra students do not change the average, which remains 1.0.
• Single class: only one class exists, so all extra students go to it. No heap logic needed, but the algorithm handles it correctly.
• Very large k: when extraStudents is much larger than the number of classes, later assignments produce negligible gains. The algorithm still works, it just takes more iterations.
• One class with 0 passing: a class like [0, 100] has the highest initial gain because the gap between total and passing is maximized. The algorithm correctly prioritizes it.
• All classes identical: when every class has the same pass and total, the gains are all equal. Students are distributed evenly across classes, which is optimal.

From understanding to recall

The greedy heap pattern here is clean: compute marginal gains, put them in a heap, pop the best, update, repeat. The logic fits in about ten lines of Python. But under interview pressure, the details matter. Do you negate the gain or the ratio? Do you update pass and total before or after recomputing the gain? Do you divide by len(heap) or len(classes) at the end?

These are not conceptual misunderstandings. They are recall gaps, and the only way to close them is practice. When you have written the gain function, the heap initialization, and the assignment loop from memory a few times, the pattern locks in. You see "distribute resources to maximize average" and the solution flows out without hesitation.

Related posts

• Kth Largest Element in an Array - Heap-based selection where you maintain a heap of size k to find the kth largest efficiently
• Task Scheduler - Greedy scheduling with frequency tracking, using a heap to always pick the most frequent remaining task
• Top K Frequent Elements - Heap for priority-based selection, combining counting with heap extraction

CodeBricks breaks Maximum Average Pass Ratio into its marginal gain calculation and max heap selection building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy heap problem shows up in your interview, you do not think about it. You just write it.