Back to blog
Dec 15, 2024
5 min read

LeetCode 1792: Maximum Average Pass Ratio

Leetcode 1792: Maximum Average Pass Ratio solution in Python

Problem Description

LeetCode Problem 1792

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

Difficulty: Medium

Tags: array, greedy, heap (priority queue)

Rating: 91.70%

Solution Approach

The key insight is that we should assign each extra student to the class where they’ll make the biggest improvement in the overall average. This naturally leads to a greedy approach using a max heap.

Algorithm:

  1. Create a max heap ordered by potential improvement
  2. For each extra student:
    • Take the class with maximum potential improvement
    • Add the student to that class
    • Recalculate and reinsert the updated class
  3. Calculate final average pass ratio

Detailed Example

Let’s walk through Example 1: classes = [[1,2],[3,5],[2,2]], extraStudents = 2

Initial state:

Class 1: 1/2 = 0.500 (improvement if added: 2/3 - 1/2 = 0.167)
Class 2: 3/5 = 0.600 (improvement if added: 4/6 - 3/5 = 0.067)
Class 3: 2/2 = 1.000 (improvement if added: 3/3 - 2/2 = 0.000)

Steps:

  1. First student goes to Class 1 (maximum improvement):

    Class 1: 2/3 = 0.667 (new improvement: 3/4 - 2/3 = 0.083)
    Class 2: 3/5 = 0.600 (improvement: 4/6 - 3/5 = 0.067)
    Class 3: 2/2 = 1.000 (improvement: 3/3 - 2/2 = 0.000)
    
  2. Second student also goes to Class 1:

    Class 1: 3/4 = 0.750
    Class 2: 3/5 = 0.600
    Class 3: 2/2 = 1.000
    

Final average: (0.750 + 0.600 + 1.000) / 3 = 0.783

Python Implementation

class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        def improvement(pass_count, total):
            """Calculate improvement in pass ratio if we add one student"""
            return (pass_count + 1)/(total + 1) - (pass_count/total)
        
        # Create max heap (using negative values since heapq is min heap)
        heap = []
        for p, t in classes:
            imp = improvement(p, t)
            heappush(heap, (-imp, p, t))
        
        # Assign each extra student
        for _ in range(extraStudents):
            imp, p, t = heappop(heap)
            # Calculate new improvement after adding a student
            new_imp = improvement(p + 1, t + 1)
            heappush(heap, (-new_imp, p + 1, t + 1))
        
        # Calculate final average
        return sum(p/t for _, p, t in heap) / len(classes)

Complexity Analysis

  • Time Complexity: O(ElogN)O(E log N), where:
    • N is the number of classes
    • E is the number of extra students
    • Each heap operation is O(log N)
  • Space Complexity: O(N)O(N) for the heap

Key Insights

  1. Greedy Choice Property: Adding a student to the class with the highest potential improvement is optimal at each step
  2. Heap Usage: Max heap efficiently gives us the class with maximum improvement potential . Improvement Formula: The improvement calculation (p+1)/(t+1) - p/t captures the marginal benefit of adding one student