Skip to main content
Talentd

Maximum Average Pass Ratio - Solution & Explanation

MediumArrayGreedyHeap (Priority Queue)16 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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:

Input: classes = [[1,2],[3,5],[2,2]], extraStudents = 2
Output: 0.78333
Explanation: You can assign the two extra students to the first class. The average pass ratio will be equal to (3/4 + 3/5 + 2/2) / 3 = 0.78333.

Example 2:

Input: classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
Output: 0.53485

 

Constraints:

  • 1 <= classes.length <= 105
  • classes[i].length == 2
  • 1 <= passi <= totali <= 105
  • 1 <= extraStudents <= 105

Approach Overview

Problem Overview: You are given several classes where pass[i] students out of total[i] passed. Extra students are guaranteed to pass their class. The goal is to assign these extra students across classes to maximize the overall average pass ratio.

Approach 1: Greedy + Priority Queue (O((n + k) log n) time, O(n) space)

The key observation: adding a student to different classes increases the pass ratio by different amounts. The gain from assigning one student to a class is (p+1)/(t+1) - p/t. Always assign the next student to the class with the largest improvement. This greedy choice ensures each step maximizes the global average increase.

Use a max heap (Heap (Priority Queue)) where each entry stores the improvement value and the class state (pass, total). Initialize the heap with all classes. Repeatedly pop the class with the highest gain, update its values after adding a student, recompute the gain, and push it back into the heap. After distributing all extra students, compute the final average pass ratio across all classes. Heap operations take O(log n), giving overall complexity O((n + k) log n).

This solution combines Greedy decision making with a Priority Queue to efficiently pick the best class each time. It scales well even when the number of extra students is large.

Approach 2: Direct Simulation (O(n * k) time, O(1) extra space)

A straightforward strategy repeatedly checks every class to determine which one benefits the most from receiving the next student. For each extra student, iterate through the entire Array of classes, compute the improvement for each class, and pick the maximum. Then update that class and continue.

This approach is easy to implement because it avoids advanced data structures. However, each allocation requires scanning all n classes. With k extra students, the total runtime becomes O(n * k), which becomes slow when both values are large.

Recommended for interviews: The greedy priority queue solution is the expected approach. It shows you can quantify marginal gain and maintain the best candidate efficiently with a heap. Discussing the direct simulation first demonstrates baseline reasoning, but implementing the heap-based greedy approach proves strong algorithmic and data structure skills.

Approach 1: Approach 1: Greedy + Priority Queue

This approach uses a priority queue (or max heap) to determine which class will benefit the most from an extra student in terms of maximizing the pass ratio. The difference in pass ratio by adding an extra student is calculated for each class, and at each step, the student is added to the class with the maximum benefit.

Initially, calculate the potential pass ratio increase for one extra student to each class, insert these into the priority queue. Pop from the queue to get the class with maximum potential increase, add an extra student, calculate the new potential increase, and push it back to the queue. Repeat until all extra students are allocated.

The code utilizes a max heap to always pop the class that gains the most from an extra student. Each class's gain is defined as the change in pass ratio if an extra student is added. After processing all extra students, the average pass ratio is calculated and returned.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O((n + extraStudents) log n) where n is the number of classes.

Space Complexity: O(n) for storing classes in the heap.

Try this approach in the editor →

Approach 2: Approach 2: Direct Simulation

This approach directly simulates the process of assigning extra students by iterating over each class and finding the gain for each possible allocation of extra students. Though less efficient, this is simpler and works within constraints when the number of classes or extra students is small.

The solution maintains a priority queue of class information using a custom comparator to prioritize classes that benefit the most from additional students. Each time a student is assigned, the ratios are recalculated.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O((n + E) * log n), where E is the number of extraStudents.

Space Complexity: O(n) for storing ratios in the priority queue.

Try this approach in the editor →

Approach 3: Priority Queue (Max-Heap of Increment)

Suppose a class currently has a pass rate of \frac{a}{b}. If we arrange a smart student into this class, then the pass rate of the class will become \frac{a+1}{b+1}. We can find that the increment of the pass rate is \frac{a+1}{b+1} - \frac{a}{b}.

We maintain a max-heap, which stores the increment of the pass rate for each class.

Perform extraStudents operations, each time taking a class from the top of the heap, adding 1 to both the number of students and the number of passes in this class, then recalculating the increment of the pass rate of this class and putting it back into the heap. Repeat this process until all students are allocated.

Finally, we sum up the pass rates of all classes, and then divide by the number of classes to get the answer.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of classes.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Greedy + Priority Queue

Time Complexity: O((n + extraStudents) log n) where n is the number of classes.

Space Complexity: O(n) for storing classes in the heap.

Approach 2: Direct Simulation

Time Complexity: O((n + E) * log n), where E is the number of extraStudents.

Space Complexity: O(n) for storing ratios in the priority queue.

Priority Queue (Max-Heap of Increment)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy + Priority QueueO((n + k) log n)O(n)General case. Efficient when many extra students must be distributed.
Direct SimulationO(n * k)O(1)Small inputs or when avoiding heap implementation.

Video Solution

Maximum Average Pass Ratio | Detailed | Covered Minute Details | Leetcode 1792 | codestorywithMIK • codestorywithMIK • 15,236 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Average Pass Ratio easy or hard?
Maximum Average Pass Ratio is rated Medium on LeetCode. The challenge comes from recognizing that each assignment has a different marginal gain and that a greedy approach with a heap efficiently tracks the best choice.
Maximum Average Pass Ratio Python/Java solution
Python solutions typically use the heapq module with negated gain values to simulate a max heap. Java implementations use PriorityQueue with a custom comparator that orders classes by improvement. Both implementations follow the same greedy heap logic and run in O((n + k) log n) time.
How to solve Maximum Average Pass Ratio in O(n)?
An exact O(n) solution is generally not used because the best class must be re-evaluated after each assignment. The standard efficient approach uses a priority queue to track the class with the maximum marginal gain. This leads to O((n + k) log n) time, which is efficient for the problem constraints.
What is the best approach for Maximum Average Pass Ratio?
The optimal solution uses a greedy strategy with a max heap (priority queue). At each step, assign the extra student to the class that produces the largest improvement in pass ratio. The improvement is calculated as (p+1)/(t+1) - p/t. Using a heap allows selecting the best class in O(log n), resulting in O((n + k) log n) total time.
Is Maximum Average Pass Ratio asked at Google/Amazon/Meta?
Greedy optimization with heaps is a common interview pattern at companies like Google, Amazon, and Meta. Variants of this problem appear in interviews to test whether candidates can compute marginal gain and maintain the best candidate using a priority queue.
What data structure is used in Maximum Average Pass Ratio?
The core data structure is a max heap (priority queue). Each heap entry stores the class along with the calculated improvement in pass ratio if one extra student is added. This structure allows efficient retrieval of the class that benefits the most from the next assignment.
What is the time complexity of Maximum Average Pass Ratio?
The optimal greedy priority queue approach runs in O((n + k) log n) time, where n is the number of classes and k is the number of extra students. Each heap push or pop operation takes O(log n). A simpler direct simulation approach takes O(n * k) time because it scans all classes for every extra student.

Ready to solve this problem?

Practice Maximum Average Pass Ratio with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays