1792. Maximum Average Pass Ratio

MediumGreedyArrayHeap (Priority Queue)
Leetcode Link

Problem Description

In the given LeetCode problem, we have a list of classes, each represented by a list of two integers where the first integer indicates the number of students that will pass the final exam and the second integer represents the total number of students in that class. Additionally, we have a certain number of extra brilliant students who are guaranteed to pass the exam in whatever class they join.

The goal is to distribute these extra students among the classes in a way that maximizes the overall average pass ratio. The pass ratio for a class is calculated as the fraction of students passing the exam over the total number of students in the class. The overall average pass ratio is the sum of individual class pass ratios divided by the total number of classes.

We are tasked with assigning the extra students and returning the highest possible average pass ratio across all classes, where answers within 10^-5 of the actual answer will be considered acceptable.

Intuition

To maximize the overall average pass ratio, we need to consider where adding an extra student would make the most significant impact. Intuitively, adding a student to a class where it will cause a more substantial increase in the pass ratio would be more beneficial than adding them to a class where the increase would be less significant. This is because the marginal gain in the pass ratio decreases as the number of students in the class increases.

To efficiently determine where to add an extra student, we can use a max heap data structure. The heap will help us prioritize the classes based on which of them would give us the highest incremental increase in the pass ratio if an extra student were added.

Here's the intuition behind the solution steps:

  1. First, we calculate the potential increase in the pass ratio for each class if we add one extra student and store this along with the current pass and total counts in a max heap. The potential increase is represented as the difference between the current pass ratio and the pass ratio if we added one student, which is (a / b - (a + 1) / (b + 1)), where a is the number of students passing and b is the total number of students.

  2. We then iterate for each extra student, popping off the class from the heap with the highest potential increase and updating that class's pass and total counts to reflect adding one extra student. We then calculate the new potential increase in the pass ratio for that class and push it back into the heap.

  3. Now with each extra student assigned to a class, we calculate the final average pass ratio by summing up the pass ratios of each class and dividing by the number of classes.

In summary, by continuously allocating extra students to the classes where they lead to the most significant relative improvement in the pass ratio, we can achieve the maximum average pass ratio across all classes.

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

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Solution Approach

The implementation of the solution uses a priority queue, represented in Python as a min heap (due to Python's heapq library natively implementing min heaps). Since we want to use this as a max heap, we store tuples with the first element being the negative of the potential increase in the pass ratio (to invert the min heap into a max heap), along with the current number of students passing and the total students for that class.

Here's how each part of the solution is implemented:

  1. Building the Max Heap: The max heap is initialized with the negative potential increase in the pass ratio of adding an extra student to each class, along with the current passing and total student counts for each class. The reason for storing the negative is that Python's heapq module provides a min heap; negating the values allows us to simulate a max heap. Thus, the line (a / b - (a + 1) / (b + 1), a, b) for each class [a, b] in classes captures the marginal gain from adding an extra student, and heapify(h) turns this list into a heap in-place for efficient access to the class with the maximum potential increase.

  2. Allocating Extra Students: We then iterate the number of extraStudents times. In each iteration, we pop from the heap to get the class with the current highest potential pass ratio increase (heappop(h)), increment the passing and total student counts (a + 1, b + 1), and push the updated class back to the heap (heappush(h, ...)) with its new potential increase.

  3. Calculating the Final Average Pass Ratio: Finally, once all the extra students have been allocated, we calculate the sum of the actual pass ratios of each class (sum(v[1] / v[2] for v in h)) and divide by the number of classes to get the average pass ratio.

The algorithm is particularly efficient because it uses a priority queue to always select the class that will benefit the most from an additional student, rather than having to recalculate and compare the pass ratio increases for all classes upon each student's assignment. This allows the solution to run in O((n + m) * log(n)) time complexity, where n is the number of classes and m is the number of extra students since each heap operation (pop and push) takes O(log(n)) time, and there are m such operations plus n operations to build the initial heap.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach outlined above. Suppose we have two classes and two extra brilliant students to distribute. The first class has 1 student who will pass out of a total of 2 students, and the second class has 2 students who will pass out of a total of 5 students. Our classes list is therefore [[1, 2], [2, 5]].

  1. Building the Max Heap:

    • For the first class, the potential increase in the pass ratio from adding an extra student is calculated by the expression ((1/2 - (1+1)/(2+1))), which equals approximately -0.1667 when taking the negative (remember we are using a min heap to simulate a max heap).
    • For the second class, the potential increase is ((2/5 - (2+1)/(5+1))), which equals approximately -0.0333.
    • The max heap, therefore, initially contains the elements [(-0.1667, 1, 2), (-0.0333, 2, 5)] after it has been heapified.

  2. Allocating Extra Students:

    • We now distribute the two extra students. For the first student, we pop the class with the highest potential increase, which is the first class, and update the counts to reflect the addition of a student. The updated class now has a passing count of 1+1 and a total count of 2+1.
    • We now recalculate the potential increase for this class, which becomes ((2/3 - (2+1)/(3+1))), or approximately -0.0833 after taking the negative, and push it back onto the heap.
    • The heap currently contains [(-0.0833, 2, 3), (-0.0333, 2, 5)].
    • For the second student, we again pop the class with the highest potential increase, which is now the first class again, and update it similarly. The updated class now has a passing count of 2+1 and a total of 3+1.
    • We recalculate the potential increase for this class, which is ((3/4 - (3+1)/(4+1))), or approximately -0.05 when taking the negative, and push it back onto the heap.
    • The heap now contains [(-0.05, 3, 4), (-0.0333, 2, 5)].

  3. Calculating the Final Average Pass Ratio:

    • With no more extra students to allocate, we calculate the final average pass ratio.
    • We sum the actual pass ratios of each updated class. The final pass ratios are (3/4) for the first class and (2/5) for the second class.
    • The sum is (3/4 + 2/5), which is 1.95/2.0.
    • We divide this sum by the total number of classes (2) to get the average pass ratio, which comes out to 0.975.

This is the highest possible average pass ratio that can be achieved by distributing the two extra students and illustrates how the max heap is used to prioritize class updates to maximize the overall average pass ratio.

Solution Implementation

1from heapq import heapify, heappop, heappush
2from typing import List
3
4class Solution:
5    def maxAverageRatio(self, classes: List[List[int]], extra_students: int) -> float:
6        # Create a max-heap based on the change in average by adding an extra student to each class
7        # The data in the heap is a tuple containing the difference in the ratio, 
8        # the number of pass students and then total number of students in that class.
9        max_heap = [(-(a / b - (a + 1) / (b + 1)), a, b) for a, b in classes]
10        # Convert the array into a heap data structure (in-place)
11        heapify(max_heap)
12
13        # Allocate extra students to the classes
14        for _ in range(extra_students):
15            # Pop the class with the maximum potential ratio increase
16            neg_delta, pass_students, total_students = heappop(max_heap)
17            # Update the student counts for that class
18            pass_students += 1
19            total_students += 1
20            # Calculate the new potential increase in average and push it back into the heap
21            new_neg_delta = -(pass_students / total_students - (pass_students + 1) / (total_students + 1))
22            heappush(max_heap, (new_neg_delta, pass_students, total_students))
23
24        # After all extra students have been allocated, calculate the total average ratio
25        total_ratio = sum(pass_students / total_students for _, pass_students, total_students in max_heap)
26        # Return the average ratio across all classes
27        return total_ratio / len(classes)
28
1import java.util.PriorityQueue;
2
3class Solution {
4    public double maxAverageRatio(int[][] classes, int extraStudents) {
5        // Priority queue to store each class using a custom comparator based on the improvement
6        // in pass ratio by adding one extra student to the class.
7        PriorityQueue<double[]> priorityQueue = new PriorityQueue<>((a, b) -> {
8            double improvementA = (a[0] + 1) / (a[1] + 1) - a[0] / a[1];
9            double improvementB = (b[0] + 1) / (b[1] + 1) - b[0] / b[1];
10            return Double.compare(improvementB, improvementA); // Max-heap, so we invert the comparison
11        });
12      
13        // Populate the priority queue with the pass ratio of each class
14        for (int[] cls : classes) {
15            priorityQueue.offer(new double[] {cls[0], cls[1]});
16        }
17      
18        // Distribute the extra students to the classes where they would cause the highest improvement
19        while (extraStudents-- > 0) {
20            double[] currentClass = priorityQueue.poll();
21            double passes = currentClass[0] + 1, totalStudents = currentClass[1] + 1;
22            priorityQueue.offer(new double[] {passes, totalStudents});
23        }
24      
25        // Calculate the total average ratio after all extra students have been distributed
26        double totalAverageRatio = 0;
27        while (!priorityQueue.isEmpty()) {
28            double[] classRatio = priorityQueue.poll();
29            totalAverageRatio += classRatio[0] / classRatio[1];
30        }
31      
32        // Return the final average ratio by dividing by the total number of classes
33        return totalAverageRatio / classes.length;
34    }
35}
36
1#include <vector>
2#include <queue>
3
4class Solution {
5public:
6    // Function to calculate the maximum average ratio after adding extra students
7    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
8        // Create a priority queue to store the potential increase in ratio and class counts
9        priority_queue<tuple<double, int, int>> potentialQueue;
10      
11        // Calculate the initial potential increase for each class and push it to the priority queue
12        for (const auto& cls : classes) {
13            int passCount = cls[0], totalCount = cls[1];
14            double potentialIncrease = static_cast<double>(passCount + 1) / (totalCount + 1) - static_cast<double>(passCount) / totalCount;
15            potentialQueue.push({potentialIncrease, passCount, totalCount});
16        }
17      
18        // Distribute extra students to classes where they would maximally increase the average ratio
19        while (extraStudents--) {
20            // Get the class with the highest potential increase
21            auto [potential, passCount, totalCount] = potentialQueue.top();
22            potentialQueue.pop();
23          
24            // Add an extra student to the class
25            passCount++;
26            totalCount++;
27
28            // Recalculate the potential increase for the updated class and push back into the queue
29            potentialIncrease = static_cast<double>(passCount + 1) / (totalCount + 1) - static_cast<double>(passCount) / totalCount;
30            potentialQueue.push({potentialIncrease, passCount, totalCount});
31        }
32      
33        // Calculate the final average ratio
34        double totalRatio = 0;
35        while (!potentialQueue.empty()) {
36            auto [_, passCount, totalCount] = potentialQueue.top();
37            potentialQueue.pop();
38            totalRatio += static_cast<double>(passCount) / totalCount;
39        }
40      
41        // Return the average ratio across all classes
42        return totalRatio / classes.size();
43    }
44};
45
1// Import statement for PriorityQueue, assuming there's a library or custom implementation for this
2// As TypeScript does not have a built-in PriorityQueue, an external library should be used,
3// or one should implement a custom PriorityQueue that supports custom comparator.
4
5import { PriorityQueue } from 'some-priority-queue-library';
6
7// Class pair structure to store classes' passCount and totalCount.
8interface ClassPair {
9    passCount: number;
10    totalCount: number;
11}
12
13// Function to calculate the potential increase in ratio
14function calculatePotentialIncrease(passCount: number, totalCount: number): number {
15    return (passCount + 1) / (totalCount + 1) - passCount / totalCount;
16}
17
18// Function to calculate the maximum average ratio after adding extra students
19function maxAverageRatio(classes: number[][], extraStudents: number): number {
20    // Create a priority queue to store the potential increase in ratio and class counts.
21    // The comparator should ensure the highest potential increase comes first.
22    const potentialQueue = new PriorityQueue<(number | ClassPair)[]>({
23        comparator: function(a, b) {
24            return a[0] > b[0];
25        }
26    });
27
28    // Calculate the initial potential increase for each class and push it to the priority queue.
29    classes.forEach(([passCount, totalCount]) => {
30        const potentialIncrease = calculatePotentialIncrease(passCount, totalCount);
31        potentialQueue.push([potentialIncrease, { passCount, totalCount }]);
32    });
33
34    // Distribute extra students to classes where they would maximally increase the average ratio.
35    while (extraStudents > 0) {
36        const [potential, classPair] = potentialQueue.pop();
37        const { passCount, totalCount } = classPair as ClassPair;
38
39        // Add an extra student to the class.
40        classPair.passCount++;
41        classPair.totalCount++;
42
43        // Recalculate the potential increase for the updated class and push back into the queue.
44        const newPotentialIncrease = calculatePotentialIncrease(classPair.passCount, classPair.totalCount);
45        potentialQueue.push([newPotentialIncrease, classPair]);
46
47        extraStudents--;
48    }
49
50    // Calculate the final average ratio.
51    let totalRatio = 0;
52    while (potentialQueue.length > 0) {
53        const [, classPair] = potentialQueue.pop();
54        const { passCount, totalCount } = classPair as ClassPair;
55        totalRatio += passCount / totalCount;
56    }
57
58    // Return the average ratio across all classes.
59    return totalRatio / classes.length;
60}
61
Not Sure What to Study? Take the 2-min Quiz：

Which of the following uses divide and conquer strategy?

Time and Space Complexity

Time Complexity

The primary operations in this code are:

  1. The initial creation and heapification of a list of tuples, which takes O(N) time, where N is the length of the classes list.
  2. Extra iterations equal to the number of extra students extraStudents. In each iteration:
    • heappop() operation, which has a time complexity of O(log N).
    • Simple arithmetic operations, followed by a heappush() operation, which also has a time complexity of O(log N).

Therefore, the time complexity for the loop that runs extraStudents times is O(extraStudents * log N).

The final computation to sum the ratios has a time complexity of O(N).

Adding all these up, the total time complexity is O(N + extraStudents * log N).

Space Complexity

The space complexity of the code is due to:

  1. The space required for heap h, which stores N tuples, so it's O(N).
  2. The space for the outputs of the arithmetic operations, which is constant O(1), as they don't depend on the size of the input and are reused in each iteration.

Therefore, the total space complexity is O(N).

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following uses divide and conquer strategy?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Heap Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫