Problem Description

You have a school with multiple classes, and each class has students taking a final exam. You're given a 2D array classes where classes[i] = [pass_i, total_i] means:

• Class i has total_i students in total
• Currently, pass_i students will pass the exam

You also have extraStudents brilliant students who are guaranteed to pass any exam. You need to assign these extra students to classes to maximize the overall average pass ratio.

Key definitions:

• Pass ratio of a class = (number of students who pass) / (total number of students)
• Average pass ratio = (sum of all class pass ratios) / (number of classes)

Your goal is to distribute the extraStudents among the classes to achieve the highest possible average pass ratio. Each extra student you add to a class increases both the number of passing students and the total number of students by 1.

For example, if a class has 3 students passing out of 5 total (ratio = 3/5 = 0.6), and you add one brilliant student, it becomes 4 students passing out of 6 total (ratio = 4/6 ≈ 0.667).

The solution uses a greedy approach with a max-heap. It calculates the "gain" or improvement in pass ratio for adding one student to each class. The gain from changing a class from a/b to (a+1)/(b+1) is (a+1)/(b+1) - a/b. The algorithm repeatedly assigns students to the class that would benefit most (highest gain) until all extra students are assigned.

Return the maximum average pass ratio achievable. Answers within 10^-5 of the actual answer are accepted.

Intuition

The key insight is that adding a student to different classes will have different impacts on the overall average. We want to maximize our return on each student placement.

Consider two classes:

• Class A: 1 student passes out of 2 (ratio = 0.5)
• Class B: 90 students pass out of 100 (ratio = 0.9)

If we add one brilliant student:

• Class A becomes 2/3 ≈ 0.667 (gain of ~0.167)
• Class B becomes 91/101 ≈ 0.901 (gain of ~0.001)

Even though Class B has a higher pass ratio, adding a student to Class A provides a much larger improvement. This reveals that we should focus on which class gets the biggest "boost" from each additional student.

The gain formula (a+1)/(b+1) - a/b measures exactly this boost. Classes with lower initial ratios and smaller total sizes tend to benefit more from additional students.

Since we want to maximize the total average, we should use a greedy strategy: always give the next student to whichever class would improve the most. This naturally leads to using a max-heap data structure, where we:

1. Calculate the potential gain for each class
2. Always pick the class with maximum gain
3. Add a student to that class
4. Recalculate its new gain (since adding more students to the same class has diminishing returns)
5. Repeat until all extra students are assigned

The greedy approach works here because each decision is independent - adding a student to one class doesn't affect the ratios of other classes, only the potential gain of the same class for future additions.

Learn more about Greedy and Heap (Priority Queue) patterns.

Solution Approach

The solution implements a greedy algorithm using a max-heap (priority queue) to efficiently track and update the gain from adding students to each class.

Step 1: Initialize the Max-Heap

We create a heap where each element is a tuple containing:

• The negative gain value (since Python's heapq is a min-heap by default, we negate to simulate max-heap)
• Current number of passing students a
• Current total number of students b

The initial gain for each class is calculated as: a/b - (a+1)/(b+1)

h = [(a / b - (a + 1) / (b + 1), a, b) for a, b in classes]
heapify(h)

Step 2: Distribute Extra Students

For each of the extraStudents, we:

1. Extract the class with maximum gain (minimum negative gain) from the heap
2. Add one brilliant student to this class (increment both a and b)
3. Recalculate the new gain for this class
4. Push the updated class back into the heap

for _ in range(extraStudents):
    _, a, b = heappop(h)
    a, b = a + 1, b + 1
    heappush(h, (a / b - (a + 1) / (b + 1), a, b))

The gain decreases with each additional student to the same class. For example, if a class goes from 3/5 to 4/6, the next gain would be 4/6 - 5/7, which is smaller than the previous gain of 3/5 - 4/6.

Step 3: Calculate Final Average

After all extra students are assigned, we calculate the average pass ratio:

• Sum all individual class ratios: sum(v[1] / v[2] for v in h)
• Divide by the number of classes: / len(classes)

return sum(v[1] / v[2] for v in h) / len(classes)

Time Complexity: O(n log n + m log n) where n is the number of classes and m is the number of extra students. The initial heapification takes O(n), and we perform m operations of heap pop and push, each taking O(log n).

Space Complexity: O(n) for storing the heap with information about all classes.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Input:

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

We have 3 classes:

• Class 0: 1/2 = 0.500 pass ratio
• Class 1: 3/5 = 0.600 pass ratio
• Class 2: 2/2 = 1.000 pass ratio

Step 1: Calculate Initial Gains and Build Max-Heap

For each class, calculate the gain from adding one student:

• Class 0: (2/3) - (1/2) = 0.667 - 0.500 = 0.167
• Class 1: (4/6) - (3/5) = 0.667 - 0.600 = 0.067
• Class 2: (3/3) - (2/2) = 1.000 - 1.000 = 0.000

Max-heap (stored as negative values): [(-0.167, 1, 2), (-0.067, 3, 5), (0.000, 2, 2)]

Step 2: Assign First Extra Student

Pop class with maximum gain (Class 0 with gain 0.167):

• Add student: Class 0 becomes 2/3
• Calculate new gain: (3/4) - (2/3) = 0.750 - 0.667 = 0.083
• Push back: (-0.083, 2, 3)

Heap state: [(-0.083, 2, 3), (-0.067, 3, 5), (0.000, 2, 2)]

Step 3: Assign Second Extra Student

Pop class with maximum gain (Class 0 again with gain 0.083):

• Add student: Class 0 becomes 3/4
• Calculate new gain: (4/5) - (3/4) = 0.800 - 0.750 = 0.050
• Push back: (-0.050, 3, 4)

Final heap: [(-0.067, 3, 5), (-0.050, 3, 4), (0.000, 2, 2)]

Step 4: Calculate Final Average

Final class configurations:

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

Average pass ratio = (0.750 + 0.600 + 1.000) / 3 = 2.350 / 3 ≈ 0.783

Notice how both extra students went to Class 0, even though it initially had the lowest pass ratio. This is because it provided the greatest improvement to the overall average each time.

Solution Implementation

Time and Space Complexity

The time complexity is O((n + k) × log n), where n is the number of classes and k is the number of extra students.

• Initial heap creation from the list comprehension: O(n) for creating the list
• heapify(h): O(n) for building the heap
• The for loop runs k times (extraStudents iterations):
  • Each heappop() operation: O(log n)
  • Each heappush() operation: O(log n)
  • Total for the loop: O(k × log n)
• Final sum calculation: O(n)

Overall time complexity: O(n + n + k × log n + n) = O(n + k × log n)

When k ≥ n, this simplifies to O(k × log n). However, the reference answer states O(n × log n), which suggests either k = O(n) (extra students is proportional to number of classes) or there's an assumption that k ≤ n in the problem context.

The space complexity is O(n).

• The heap h stores one tuple for each class: O(n)
• No additional significant space is used beyond the heap

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Gain Calculation Direction

One of the most common mistakes is calculating the gain in the wrong direction. Since we want to maximize the improvement, we need to calculate how much the ratio increases when adding a student.

Wrong approach:

gain = current_ratio - new_ratio  # This gives negative gain for improvement

Correct approach:

gain = new_ratio - current_ratio  # Positive gain for improvement
# Then negate for max-heap: -gain

Or directly calculate for min-heap usage:

gain = current_ratio - new_ratio  # Negative value, smaller means better

2. Heap Initialization Error

Another pitfall is incorrectly structuring the heap tuple, which can lead to wrong comparisons or index errors when extracting values.

Wrong approach:

# Missing gain calculation or wrong tuple order
heap = [(pass_count, total_count) for pass_count, total_count in classes]

Correct approach:

heap = []
for pass_count, total_count in classes:
    gain = pass_count / total_count - (pass_count + 1) / (total_count + 1)
    heap.append((gain, pass_count, total_count))
heapify(heap)

3. Integer Division Instead of Float Division

In Python 2 or when not careful with division, integer division can cause precision loss.

Wrong approach (Python 2 style):

gain = pass_count / total_count  # May perform integer division

Correct approach:

gain = pass_count / total_count  # Python 3 automatically uses float division
# Or explicitly: float(pass_count) / total_count

4. Not Recalculating Gain After Each Addition

A critical mistake is reusing the same gain value or incorrectly calculating the new gain after adding a student.

Wrong approach:

for _ in range(extraStudents):
    _, pass_count, total_count = heappop(heap)
    pass_count += 1
    total_count += 1
    # Reusing old gain formula or not updating it
    heappush(heap, (gain, pass_count, total_count))  # 'gain' is stale

Correct approach:

for _ in range(extraStudents):
    _, pass_count, total_count = heappop(heap)
    pass_count += 1
    total_count += 1
    # Recalculate gain with updated values
    new_gain = pass_count / total_count - (pass_count + 1) / (total_count + 1)
    heappush(heap, (new_gain, pass_count, total_count))

5. Floating Point Precision Issues

When dealing with ratios and divisions, floating-point arithmetic can introduce small errors that might affect the final result.

Potential issue:

# Multiple divisions can accumulate rounding errors
ratio = pass_count / total_count
new_ratio = (pass_count + 1) / (total_count + 1)
gain = ratio - new_ratio

Better approach (though the original is usually sufficient):

# Calculate gain in one expression to minimize intermediate rounding
gain = (pass_count * (total_count + 1) - total_count * (pass_count + 1)) / (total_count * (total_count + 1))
# Simplifies to: (pass_count - total_count) / (total_count * (total_count + 1))

However, for this problem, the standard floating-point calculation is acceptable since the answer tolerance is 10^-5.