Abstract / Summary

Given student pass ratios and their group sizes, find the highest possible average pass ratio achievable by selecting certain groups.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 74% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Greedy
• Heap (Priority Queue)

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of maximizing the average pass ratio across a collection of classes after distributing a given number of extra students. Each class is represented by a pair [passed, total]. Adding an extra student to a class increases both the number of passed students and the total enrollment, thereby potentially raising the class’s pass ratio. The algorithm repeatedly assigns each extra student to the class where the marginal gain in the overall average is greatest, using a priority queue to identify that class efficiently.

Key Steps

The first important fragment defines a helper that computes the incremental improvement obtained by adding one student to a class.

gain = lambda pas, total: (pas + 1) / (total + 1) - pas / total

This expression captures the difference between the new ratio after the addition and the current ratio. It is used as the priority metric.

Next, the code builds a max-heap (implemented as a min-heap with negated gains) containing only those classes that are not already perfect (i.e., passed < total). While populating the heap, it also accumulates the initial sum of pass ratios.

worst  = []
result = 0
for pas, total in classes:
    if pas < total:
        heappush(worst, (-gain(pas, total), total, pas))
        result += pas / total
    else:
        result += 1

If every class already has a perfect pass ratio, the function returns 1 immediately.

if not worst:
    return 1

The core loop distributes the extra students. For each iteration, the class with the largest potential gain (the top of the heap) is extracted, its ratio contribution is removed from the running total, the class is updated by incrementing both passed and total, the new ratio is added back to the total, and the class is re-inserted with its updated gain.

for i in range(extraStudents):
    g, total, pas = worst[0]
    result -= pas / total
    pas    += 1
    total  += 1
    result += pas / total
    heappushpop(worst, (-gain(pas, total), total, pas))

Finally, the function returns the average ratio by dividing the accumulated sum by the number of classes.

return result / len(classes)

Edge Cases Handled

When a class already has a perfect pass ratio (passed == total), the algorithm excludes it from the heap because adding another student would not improve the ratio; the contribution to the overall sum is simply 1. This prevents unnecessary heap operations for such classes.

If the input list contains only perfect classes, the heap remains empty. The early return return 1 correctly yields the maximum possible average without entering the distribution loop.

The lambda gain safely handles the division by zero scenario because total is always at least 1 for any valid class entry, and the function never calls gain with a zero denominator.

When extraStudents is zero, the distribution loop is skipped, and the function returns the average of the original ratios, which is the correct behavior.

Performance Optimizations

The algorithm leverages a priority queue to always select the class with the highest marginal gain in O(log n) time per extra student, where n is the number of non-perfect classes. By storing the negative gain, it reuses Python’s heapq (a min-heap) as a max-heap without extra overhead.

The initial pass through classes computes both the heap and the baseline sum of ratios in a single traversal, avoiding a separate aggregation step.

During each iteration of the distribution loop, the code updates the running total result incrementally: it subtracts the old ratio and adds the new ratio directly, rather than recomputing the entire sum after each insertion. This incremental update eliminates an O(n) recomputation per iteration, keeping the overall runtime proportional to extraStudents * log n.

The use of heappushpop combines a push and a pop into a single operation, reducing the number of heap adjustments compared to separate heappush followed by heappop. This subtle choice trims constant-factor overhead in the tight loop that processes each extra student.

Imagine having a bunch of classrooms filled with students. Some students have passed their tests and some have not. There is a way to measure how well each class is doing by looking at the fraction of students who passed. When a new student joins a class, they can help improve that score.

The code looks at every classroom to see which one gets the biggest boost if another student joins it. Think of it like deciding which class would be happiest to have one more helper. First, the code calculates how much each class would improve if it received one extra student. It saves these possibilities in a special pile so the most helpful choice is always right on top.

Once the pile is ready, the code starts giving out extra students one by one. It picks the class that gets the biggest improvement, updates that class score, and then checks again to see which class needs the next extra student the most. It keeps doing this until all the extra students are placed in the classrooms where they can do the most good. By the time it finishes, it has balanced everything out so that the overall average of all the classes is as high as it can possibly be.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python						TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python				Go	Rust	TS
	Progiez	C++	Java	Python
github	black-shadows	C++
	charles-wangkai		Java
	everthis				JS
	FelixFan1122		Java
	fsq	C++
	haoel	C++
	JoshCrozier				JS
	lkwq007			Python
	MacJim	C++
	Shamik07					Dart
	suxrobGM						C#
	trung-hn			Python
	varunu28		Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
FelixFan1122	Java
fsq	C++
haoel	C++
JoshCrozier	JavaScript
lkwq007	Python
MacJim	C++
Shamik07	Dart
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality