LeetCode 1792 - Maximum Average Pass Ratio

The problem gives us several classes, where each class is represented as [passi, totali]. The value passi tells us how many students currently pass the exam, while totali tells us the total number of students in that class.

leetcodemediumarraygreedyheap-(priority-queue)

LeetCode Problem 1792

Difficulty: 🟡 Medium
Topics: Array, Greedy, Heap (Priority Queue)

Solution

Problem Understanding

The problem gives us several classes, where each class is represented as [passi, totali]. The value passi tells us how many students currently pass the exam, while totali tells us the total number of students in that class.

The pass ratio of a class is:

$\frac{pass_i}{total_i}$

We are also given extraStudents, and every extra student is guaranteed to pass whichever class they are assigned to. If we add one extra student to a class, both the number of passing students and the total number of students increase by one.

For example, if a class is [3,5], then after adding one guaranteed passing student it becomes [4,6].

The goal is to distribute all extra students across the classes so that the final average pass ratio is as large as possible.

The average pass ratio is:

$\frac{1}{n}\sum_{i=1}^{n}\frac{pass_i}{total_i}$

where n is the number of classes.

The constraints are large:

  • Up to 10^5 classes
  • Up to 10^5 extra students

These limits immediately tell us that expensive repeated scanning approaches will not work. Any solution worse than roughly O((n + extraStudents) log n) will likely time out.

An important observation is that adding a student to different classes gives different improvements. A class with a low pass ratio may benefit more from an extra passing student than a class that is already near perfect.

The problem guarantees:

  • Every class has at least one passing student
  • passi <= totali
  • There is at least one extra student

Important edge cases include:

  • Classes that already have ratio 1.0, such as [5,5]
  • Only one class in the input
  • Large numbers of extra students repeatedly assigned to the same class
  • Multiple classes having identical gains
  • Very uneven class sizes

A naive implementation can easily become too slow if it recomputes gains inefficiently.

Approaches

Brute Force Approach

The brute force idea is straightforward. For every extra student, we try assigning that student to every class and compute which assignment produces the largest increase in the average pass ratio.

The increase obtained by adding one student to a class [p, t] is:

$\left(\frac{p+1}{t+1}\right)-\left(\frac{p}{t}\right)$

For each extra student:

  1. Iterate through all classes
  2. Compute the gain for each class
  3. Choose the class with the maximum gain
  4. Update that class

This works because each step greedily chooses the locally best improvement.

However, this approach is too slow. If we have n classes and k extra students, then we perform a full scan of all classes for every student.

That results in O(n * k) time complexity, which can become 10^10 operations in the worst case.

Optimal Approach

The key insight is that we always need quick access to the class that currently provides the maximum improvement.

This is exactly the kind of problem a max heap, or priority queue, is designed for.

For every class, we compute its current marginal gain:

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

We store classes in a max heap ordered by this gain.

Then for each extra student:

  1. Extract the class with the highest gain
  2. Add the student to that class
  3. Recompute the gain
  4. Push the updated class back into the heap

This avoids repeatedly scanning all classes.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n * extraStudents) O(1) Repeatedly scans all classes for every student
Optimal O((n + extraStudents) log n) O(n) Uses a max heap to efficiently retrieve best gain

Algorithm Walkthrough

  1. Define a helper function that computes the gain obtained by adding one passing student to a class.

For a class with p passing students and t total students, the gain is:

$\left(\frac{p+1}{t+1}\right)-\left(\frac{p}{t}\right)$

This value tells us how much the class ratio improves if we place the next extra student there. 2. Build a max heap containing all classes.

Python's heapq is a min heap by default, so we store negative gains to simulate max heap behavior.

Each heap entry stores:

  • Current gain
  • Passing students
  • Total students
  1. Repeatedly assign extra students.

While we still have extra students:

  • Pop the class with the maximum gain

  • Add one student, meaning:

  • pass += 1

  • total += 1

  • Recompute the gain for the updated class

  • Push the updated class back into the heap

This guarantees that each extra student goes where it improves the average the most at that moment. 4. Compute the final average.

After all assignments are complete:

  • Sum all class ratios from the heap
  • Divide by the number of classes

Why it works

The algorithm works because at every step we choose the class with the maximum marginal improvement. The gain from assigning a student to a class decreases as more students are added, which creates a greedy structure suitable for a priority queue.

The heap always contains the correct next best choice, so repeatedly selecting the maximum gain produces the globally optimal result.

Python Solution

from typing import List
import heapq

class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        
        def gain(passed: int, total: int) -> float:
            return (passed + 1) / (total + 1) - passed / total

        max_heap = []

        for passed, total in classes:
            current_gain = gain(passed, total)
            heapq.heappush(max_heap, (-current_gain, passed, total))

        for _ in range(extraStudents):
            negative_gain, passed, total = heapq.heappop(max_heap)

            passed += 1
            total += 1

            updated_gain = gain(passed, total)
            heapq.heappush(max_heap, (-updated_gain, passed, total))

        total_ratio = 0.0

        while max_heap:
            _, passed, total = heapq.heappop(max_heap)
            total_ratio += passed / total

        return total_ratio / len(classes)

The implementation begins with a helper function called gain, which computes how much improvement a class receives when one guaranteed passing student is added.

A heap is then created to store all classes. Since Python only provides a min heap, negative gains are used so that the largest gain behaves like the smallest value in heap ordering.

Each iteration assigns one extra student. The class with the largest gain is removed from the heap, updated, and inserted again with its new gain value.

Finally, after all assignments are complete, the code computes the average pass ratio by summing the ratios of all classes and dividing by the number of classes.

Go Solution

package main

import (
	"container/heap"
)

type Class struct {
	gain   float64
	passed int
	total  int
}

type MaxHeap []Class

func (h MaxHeap) Len() int {
	return len(h)
}

func (h MaxHeap) Less(i, j int) bool {
	return h[i].gain > h[j].gain
}

func (h MaxHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(Class))
}

func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

func gain(passed int, total int) float64 {
	return float64(passed+1)/float64(total+1) -
		float64(passed)/float64(total)
}

func maxAverageRatio(classes [][]int, extraStudents int) float64 {
	h := &MaxHeap{}

	for _, class := range classes {
		passed := class[0]
		total := class[1]

		heap.Push(h, Class{
			gain:   gain(passed, total),
			passed: passed,
			total:  total,
		})
	}

	for extraStudents > 0 {
		best := heap.Pop(h).(Class)

		best.passed++
		best.total++
		best.gain = gain(best.passed, best.total)

		heap.Push(h, best)

		extraStudents--
	}

	totalRatio := 0.0

	for h.Len() > 0 {
		current := heap.Pop(h).(Class)
		totalRatio += float64(current.passed) / float64(current.total)
	}

	return totalRatio / float64(len(classes))
}

The Go implementation uses the container/heap package to implement a max heap. Since Go's heap interface is customizable, the Less function is reversed so that larger gains have higher priority.

Unlike Python, Go requires explicit heap type definitions and interface methods. Floating point division also requires explicit conversion using float64.

The logic itself is identical to the Python solution.

Worked Examples

Example 1

Input:

classes = [[1,2],[3,5],[2,2]]
extraStudents = 2

Initial gains:

Class Current Ratio Ratio After Add Gain
[1,2] 0.5 0.6667 0.1667
[3,5] 0.6 0.6667 0.0667
[2,2] 1.0 1.0 0.0

Heap top is [1,2].

First extra student

Assign to [1,2]:

[1,2] -> [2,3]

Updated gains:

Class New Gain
[2,3] 0.0833
[3,5] 0.0667
[2,2] 0.0

Heap top remains [2,3].

Second extra student

Assign to [2,3]:

[2,3] -> [3,4]

Final classes:

Class Ratio
[3,4] 0.75
[3,5] 0.6
[2,2] 1.0

Average:

(0.75 + 0.6 + 1.0) / 3
= 0.78333

Example 2

Input:

classes = [[2,4],[3,9],[4,5],[2,10]]
extraStudents = 4

Initial gains:

Class Gain
[2,4] 0.1000
[3,9] 0.0667
[4,5] 0.0333
[2,10] 0.0727

The algorithm repeatedly selects the current highest gain class.

Assignments occur in this order:

  1. [2,4] -> [3,5]
  2. [2,10] -> [3,11]
  3. [3,5] -> [4,6]
  4. [3,11] -> [4,12]

Final average becomes approximately:

0.53485

Complexity Analysis

Measure Complexity Explanation
Time O((n + extraStudents) log n) Heap operations take logarithmic time
Space O(n) Heap stores all classes

Building the initial heap requires O(n) insertions. Each extra student causes one pop and one push operation, both costing O(log n).

Therefore the total complexity is:

O(n log n + extraStudents log n)

which simplifies to:

O((n + extraStudents) log n)

The heap stores one entry per class, so the auxiliary space usage is linear.

Test Cases

from typing import List
import math

class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        import heapq

        def gain(passed: int, total: int) -> float:
            return (passed + 1) / (total + 1) - passed / total

        heap = []

        for passed, total in classes:
            heapq.heappush(heap, (-gain(passed, total), passed, total))

        for _ in range(extraStudents):
            _, passed, total = heapq.heappop(heap)

            passed += 1
            total += 1

            heapq.heappush(heap, (-gain(passed, total), passed, total))

        result = 0.0

        while heap:
            _, passed, total = heapq.heappop(heap)
            result += passed / total

        return result / len(classes)

solution = Solution()

# Provided example 1
assert math.isclose(
    solution.maxAverageRatio([[1, 2], [3, 5], [2, 2]], 2),
    0.78333,
    rel_tol=1e-5
)

# Provided example 2
assert math.isclose(
    solution.maxAverageRatio([[2, 4], [3, 9], [4, 5], [2, 10]], 4),
    0.53485,
    rel_tol=1e-5
)

# Single class only
assert math.isclose(
    solution.maxAverageRatio([[1, 2]], 1),
    2 / 3,
    rel_tol=1e-5
)

# Already perfect ratio
assert math.isclose(
    solution.maxAverageRatio([[5, 5]], 10),
    1.0,
    rel_tol=1e-5
)

# Multiple identical classes
assert math.isclose(
    solution.maxAverageRatio([[1, 2], [1, 2]], 2),
    2 / 3,
    rel_tol=1e-5
)

# Large extraStudents concentrated on one class
result = solution.maxAverageRatio([[1, 1000], [10, 10]], 100)
assert result > 0.5

# Minimum values
assert math.isclose(
    solution.maxAverageRatio([[1, 1]], 1),
    1.0,
    rel_tol=1e-5
)

# Uneven class sizes
result = solution.maxAverageRatio([[1, 100], [50, 60], [99, 100]], 20)
assert result > 0.7
Test Why
[[1,2],[3,5],[2,2]], 2 Validates the first official example
[[2,4],[3,9],[4,5],[2,10]], 4 Validates the second official example
[[1,2]], 1 Tests single class behavior
[[5,5]], 10 Ensures perfect ratios remain perfect
[[1,2],[1,2]], 2 Tests tie handling between classes
Large extra students Ensures repeated heap updates work correctly
[[1,1]], 1 Tests minimum input size
Uneven class sizes Validates gain calculations across very different totals

Edge Cases

One important edge case is when a class already has a perfect pass ratio, such as [5,5]. Adding another guaranteed passing student changes the class to [6,6], which still has ratio 1.0. The gain becomes zero, so the heap naturally deprioritizes these classes unless all classes are already perfect.

Another important case is when there is only one class. In this scenario, every extra student must go into the same class. The algorithm still works correctly because the heap simply contains one entry that is repeatedly updated.

A third tricky case occurs when multiple classes have identical gains. Some implementations incorrectly assume gains are unique. The heap handles ties naturally because any tied class can be selected without affecting correctness.

A final edge case involves very large totals, such as [1,100000]. Floating point precision becomes important here because gains may be very small. Both implementations use floating point arithmetic carefully and rely on the problem's accepted precision threshold of 10^-5.