Skip to main content

Heaps

Maximum Average Pass Ratio Solution In C++/Java/Python/Javascript

Problem Description

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

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.


Input: classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
Output: 0.53485

Constraints

  • 1 <= classes.length <= 10^5
  • classes[i].length == 2
  • 1 <= passi <= totali <= 10^5
  • 1 <= extraStudents <= 10^5
💡
Try it Yourself First
To maximize the average pass ratio, compute the incremental gain (marginal improvement) of adding an extra passing student to each class. Then, use a max-heap (priority queue) to greedily allocate extra students to the class with the highest improvement at each step, updating the gains as you proceed.

Brute Force Approach

Intuition

Our main goal is to maximize the overall pass rate across all classes by strategically adding a set number of extra students. To achieve this, we need to determine where each additional student will create the maximum impact on improving the pass rate. This means carefully evaluating how much each class's pass rate would improve if we added just one more student.
We begin by calculating the current pass rate for each class, which is the ratio of passing students to total students in that class. This gives us our baseline to measure improvements against.
With these ratios in hand, we examine each class individually to determine how much the pass rate would increase if we added one student. By comparing these potential improvements across all classes, we can pinpoint which class would gain the most benefit from an extra student. This strategic approach ensures that each additional student is placed where they'll make the greatest difference to the overall pass rate.
Each time we place a student in the class that shows the highest potential benefit, we need to update that class's pass rate and recalculate. Then we repeat this entire evaluation process for the next student. This methodical approach continues until we've successfully placed all our extra students.
The beauty of this strategy is that it evaluates all possible placements at each step, ensuring we make the optimal choice for each student. However, we should note that as the number of classes and students grows larger, the calculations we need to perform increase significantly. While this makes our solution more complex for larger inputs, it's necessary to find the truly optimal distribution.
After we've placed all students and updated the pass rates accordingly, we calculate the final average pass rate across all classes to see the overall improvement we've achieved.

Maximum Average Pass Ratio – Overview

Imagine a school where each class has students preparing for their final exams. Some students are expected to pass, while others may fail. Now, you have a few extra brilliant students who are guaranteed to pass, and you can assign them to any class. The goal is to maximize the overall average pass ratio across all classes after distributing these extra students.

The pass ratio for a class is calculated as:
Pass Ratio=Total Students/Passed Students

The average pass ratio is the sum of all class pass ratios divided by the number of classes:

Average Pass Ratio=∑Pass Ratios of All Classes / Number of Classes ​

To maximize this, we should assign each extra student to the class where their addition results in the highest increase in pass ratio. For example, adding a student to a class with fewer passing students may have a bigger impact than adding them to a class that already has a high pass ratio.

Maximum Average Pass Ratio Algorithm

Step 1: Initialize Pass Ratios

  • Create an array passRatios to store the initial pass ratio for each class.
  • For each class in classes, compute the ratio of passed students to total students and store it in passRatios.

Step 2:Distribute Extra Students

  • While extraStudents is greater than zero, perform the following steps:
    -Decrement extraStudents by 1.
    -Create an updatedRatios array to store the new pass ratios if an extra student is added to each class.

Step 3:Compute Updated Ratios

  • For each class in classes:
    -Calculate the new pass ratio after adding one extra student.
    -Store this updated ratio in updatedRatios.

Step 4:Find the Best Class to Update

  • Initialize bestClassIndex = 0 and maximumGain = 0.
  • For each class, compute the gain in pass ratio:
    -Subtract the current ratio from the updated ratio.
    -If the gain is greater than maximumGain, update bestClassIndex and maximumGain accordingly.

Step 5: Update the Selected Class

  • Increment the passed students and total students for the selected class.
  • Update passRatios with the new ratio for the selected class.

Step 6: Compute Final Average Pass Ratio

  • Initialize totalPassRatio = 0.
  • Sum all the values in passRatios.
  • Return the average pass ratio by dividing totalPassRatio by the number of classes.

Dry Run

Input:

  • Classes: [[1,2], [3,5], [2,2]]
  • Extra Students: 2

Step 1: Initialize Pass Ratios

  • Calculate the initial pass ratios for each class:
  • Class 0: 1/2 = 0.5
  • Class 1: 3/5 = 0.6
  • Class 2: 2/2 = 1.0
  • Store in passRatios = [0.5, 0.6, 1.0].

Step 2: Distribute Extra Students

  • We have extraStudents = 2.
  • First Extra Student (extraStudents = 2):
  • Compute the improvement in pass ratio for each class when adding one student:
  • Class 0: (2/3 - 1/2) ≈ 0.1667 (Maximum improvement)
  • Class 1: (4/6 - 3/5) ≈ 0.0667
  • Class 2: 0.0 (No improvement since it's already 1.0)
  • The best class to update is Class 0.
  • Update Class 0 → Becomes [2,3]
  • Update passRatios → [2/3, 0.6, 1.0] ≈ [0.6667, 0.6, 1.0]
  • Decrement extraStudents → extraStudents = 1
  • Second Extra Student (extraStudents = 1):
  • Recalculate improvements with updated passRatios:
  • Class 0 (now [2,3]): (3/4 - 2/3) ≈ 0.0833 (Maximum improvement)
  • Class 1: (4/6 - 3/5) ≈ 0.0667
  • Class 2: 0.0
  • The best class to update is Class 0 again.
  • Update Class 0 → Becomes [3,4]
  • Update passRatios → [3/4, 0.6, 1.0] ≈ [0.75, 0.6, 1.0]
  • Decrement extraStudents → extraStudents = 0

Step 3: Compute Final Average Pass Ratio

  • Sum of pass ratios:0.75+0.6+1.0=2.35
  • Average pass ratio:2.35/3≈0.78333
  • Final Output: 0.78333
Code for All Languages
C++ 
// Approach: Greedy Algorithm with Brute Force  
// Language: C++  

class Solution {  
public:  
    // Function to maximize the average pass ratio by distributing extra students optimally  
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {  
        vector<double> passRatios;  

        // Step 1: Compute initial pass ratios for each class  
        for (int classIndex = 0; classIndex < classes.size(); classIndex++) {  
            double initialRatio = classes[classIndex][0] / (double)classes[classIndex][1];  
            passRatios.push_back(initialRatio);  
        }  

        // Step 2: Distribute extra students one by one  
        while (extraStudents--) {  
            vector<double> updatedRatios;  

            // Step 3: Calculate new pass ratios if an extra student is added  
            for (int classIndex = 0; classIndex < classes.size(); classIndex++) {  
                double newRatio = (classes[classIndex][0] + 1) / (double)(classes[classIndex][1] + 1);  
                updatedRatios.push_back(newRatio);  
            }  

            int bestClassIndex = 0;  
            double maximumGain = 0;  

            // Step 4: Find the class where an extra student gives the maximum improvement  
            for (int classIndex = 0; classIndex < updatedRatios.size(); classIndex++) {  
                double gain = updatedRatios[classIndex] - passRatios[classIndex];  
                if (gain > maximumGain) {  
                    bestClassIndex = classIndex;  
                    maximumGain = gain;  
                }  
            }  

            // Step 5: Update the selected class with the extra student  
            passRatios[bestClassIndex] = updatedRatios[bestClassIndex];  
            classes[bestClassIndex][0]++;  
            classes[bestClassIndex][1]++;  
        }  

        // Step 6: Compute the final average pass ratio  
        double totalPassRatio = 0;  
        for (double passRatio : passRatios) {  
            totalPassRatio += passRatio;  
        }  

        // Step 7: Return the average pass ratio across all classes  
        return totalPassRatio / classes.size();  
    }  
};

Java 
// Approach: Greedy Algorithm with Brute Force  
// Language: Java  

class Solution {  

    // Function to maximize the average pass ratio by distributing extra students optimally  
    public double maxAverageRatio(int[][] classes, int extraStudents) {  
        List<Double> passRatios = new ArrayList<>();  

        // Step 1: Compute initial pass ratios for each class  
        for (int classIndex = 0; classIndex < classes.length; classIndex++) {  
            double initialRatio = (double) classes[classIndex][0] / classes[classIndex][1];  
            passRatios.add(initialRatio);  
        }  

        // Step 2: Distribute extra students one by one  
        while (extraStudents > 0) {  
            List<Double> updatedRatios = new ArrayList<>();  

            // Step 3: Calculate new pass ratios if an extra student is added  
            for (int classIndex = 0; classIndex < classes.length; classIndex++) {  
                double newRatio = (double) (classes[classIndex][0] + 1) / (classes[classIndex][1] + 1);  
                updatedRatios.add(newRatio);  
            }  

            int bestClassIndex = 0;  
            double maximumGain = 0;  

            // Step 4: Find the class where an extra student gives the maximum improvement  
            for (int classIndex = 0; classIndex < updatedRatios.size(); classIndex++) {  
                double gain = updatedRatios.get(classIndex) - passRatios.get(classIndex);  
                if (gain > maximumGain) {  
                    bestClassIndex = classIndex;  
                    maximumGain = gain;  
                }  
            }  

            // Step 5: Update the selected class with the extra student  
            passRatios.set(bestClassIndex, updatedRatios.get(bestClassIndex));  
            classes[bestClassIndex][0]++;  
            classes[bestClassIndex][1]++;  

            extraStudents--;  
        }  

        // Step 6: Compute the final average pass ratio  
        double totalPassRatio = 0;  
        for (double passRatio : passRatios) {  
            totalPassRatio += passRatio;  
        }  

        // Step 7: Return the average pass ratio across all classes  
        return totalPassRatio / classes.length;  
    }  
}

Python 
class Solution(object):
    # Function to maximize the average pass ratio by distributing extra students optimally
    def maxAverageRatio(self, classes, extraStudents):
        """
        :type classes: List[List[int]]
        :type extraStudents: int
        :rtype: float
        """
        pass_ratios = []

        # Step 1: Compute initial pass ratios for each class
        for class_ in classes:
            initial_ratio = float(class_[0]) / class_[1]
            pass_ratios.append(initial_ratio)

        # Step 2: Distribute extra students one by one
        while extraStudents > 0:
            updated_ratios = []

            # Step 3: Calculate new pass ratios if an extra student is added
            for class_ in classes:
                new_ratio = float(class_[0] + 1) / (class_[1] + 1)
                updated_ratios.append(new_ratio)

            best_class_index = 0
            maximum_gain = 0

            # Step 4: Find the class where an extra student gives the maximum improvement
            for i in range(len(updated_ratios)):
                gain = updated_ratios[i] - pass_ratios[i]
                if gain > maximum_gain:
                    best_class_index = i
                    maximum_gain = gain

            # Step 5: Update the selected class with the extra student
            pass_ratios[best_class_index] = updated_ratios[best_class_index]
            classes[best_class_index][0] += 1
            classes[best_class_index][1] += 1

            extraStudents -= 1

        # Step 6: Compute the final average pass ratio
        total_pass_ratio = sum(pass_ratios)

        # Step 7: Return the average pass ratio across all classes
        return total_pass_ratio / len(classes)

Javascript 
/**
 * Approach: Greedy Algorithm with Brute Force
 * Language: JavaScript
 *
 * @param {number[][]} classes - Array of classes where each class contains [pass, total] students.
 * @param {number} extraStudents - Number of extra students available to distribute.
 * @return {number} - Maximum possible average pass ratio.
 */
var maxAverageRatio = function(classes, extraStudents) {
    let passRatios = [];

    // Step 1: Compute initial pass ratios for each class
    for (let i = 0; i < classes.length; i++) {
        let initialRatio = classes[i][0] / classes[i][1];
        passRatios.push(initialRatio);
    }

    // Step 2: Distribute extra students one by one
    while (extraStudents > 0) {
        let updatedRatios = [];

        // Step 3: Calculate new pass ratios if an extra student is added
        for (let i = 0; i < classes.length; i++) {
            let newRatio = (classes[i][0] + 1) / (classes[i][1] + 1);
            updatedRatios.push(newRatio);
        }

        let bestClassIndex = 0;
        let maximumGain = 0;

        // Step 4: Find the class where an extra student gives the maximum improvement
        for (let i = 0; i < updatedRatios.length; i++) {
            let gain = updatedRatios[i] - passRatios[i];
            if (gain > maximumGain) {
                bestClassIndex = i;
                maximumGain = gain;
            }
        }

        // Step 5: Update the selected class with the extra student
        passRatios[bestClassIndex] = updatedRatios[bestClassIndex];
        classes[bestClassIndex][0]++;
        classes[bestClassIndex][1]++;

        extraStudents--;
    }

    // Step 6: Compute the final average pass ratio
    let totalPassRatio = passRatios.reduce((sum, ratio) => sum + ratio, 0);

    // Step 7: Return the average pass ratio across all classes
    return totalPassRatio / classes.length;
};

Time Complexity Analysis: O(n * k)

Initial Pass Ratios Calculation (O(n))

  • You iterate through n classes once to compute the initial pass ratios.
  • Time Complexity: O(n)

Extra Students Distribution (O(k * n))

  • You iterate k times (once per extra student).
  • In each iteration:
    You compute new pass ratios for all n classes → O(n)
    You find the best class with the highest gain → O(n)
    You update the selected class (constant time) → O(1)
  • Since this entire process runs k times, the total complexity is O(k * n).

Final Time Complexity: O(n) + O(k * n) = O(n * k)

Space Complexity Analysis: O(n)

Auxiliary Space Complexity: O(n)

  • We maintain a passRatios array of size n to store pass ratios.
  • We also use an updatedRatios array of size n to store updated ratios.
  • Other variables such as bestClassIndex and maximumGain use only O(1) space.
  • Total Auxiliary Space Complexity: O(n)

Total Space Complexity: O(n)

  • The input array classes takes O(n) space.
  • The extra space used by the algorithm is also O(n) (from the two arrays).

Final Space Complexity: O(n)+O(n)=O(n)

Why is the Brute Force Approach Computationally Expensive? (TLE Issue)

Exponential Growth

  • At each step, we evaluate all n classes to determine the best one for adding a student.
  • We repeat this for k extra students.
  • This results in O(n × k) operations, which can be extremely slow when n, k ≤ 100,000.
  • In the worst case, 100,000 × 100,000 = 10 billion operations, leading to TLE (Time Limit Exceeded).

Why Does This Cause TLE?

  • When n = 100,000 and k = 100,000, brute force runs in O(n × k) = O(10⁹).
  • This exceeds the time limit (typically 10⁸ operations per second).
  • A heap-based solution reduces this to O(n + k log n), which is much faster.
The brute force approach for Maximum Average Pass Ratio becomes computationally expensive for larger inputs, prompting a transition to a Priority Queue (Max Heap) approach. This optimization enables logarithmic-time selection of classes with the highest pass ratio improvement potential, replacing linear searching with an efficient sorting mechanism. By prioritizing classes based on marginal improvement, the method streamlines student distribution while maintaining the core strategy of maximizing average pass ratio.

Optimal Approach

Intuition

The initial approach used an array and a tracking variable, maximumGain, to record the maximum difference between the new and old pass ratios. However, this led to TLE due to an extra loop for finding the maximum difference. To optimize, we eliminate the loop by using a priority queue.

First, we define a function, calculateGain, to measure how much the pass ratio improves if an extra student is added. This provides a consistent metric for comparison. Next, we use a max heap to efficiently track the class with the highest gain. Each class is stored as a tuple with its negative gain (to simulate a max heap using Python’s min heap), along with its current passed and total students. This ensures that the most impactful class is always at the top.

We then distribute extra students iteratively. At each step, we pop the class with the highest potential gain, add a student, update its pass count, recalculate the gain, and push it back into the heap. This dynamic adjustment ensures efficient allocation without re-scanning all classes.

Once all students are assigned, we compute the final result by summing up all pass ratios from the heap and dividing by the number of classes to get the average pass ratio.

Approach

Step 1: Define the Gain Function

  • Define a lambda function calculateGain(passes, totalStudents) to compute the improvement in pass ratio when adding an extra student:
    Gain=(passes+1)/(totalStudents+1)− passes/totalStudents

Step 2: Initialize the Max Heap

  • Create a max heap (maxHeap) to store tuples in the form (-gain, passes, totalStudents). The negative gain ensures the class with the highest gain appears at the top.

Step 3: Populate the Heap

  • For each class (passes, totalStudents), compute the gain using calculateGain, then push (-gain, passes, totalStudents) into maxHeap.

Step 4: Distribute Extra Students
While there are extraStudents left:

  • Decrement extraStudents by 1.
  • Pop the class with the highest potential gain from maxHeap.
  • Extract passes and totalStudents from the popped element.
  • Add one more student to this class (passes += 1, totalStudents += 1).
  • Recalculate the new gain for this updated class.
  • Push the updated tuple (-newGain, passes, totalStudents) back into maxHeap.

Step 5: Compute the Final Average Pass Ratio
Initialize totalPassRatio = 0.
While maxHeap is not empty:

  • Pop each class and add its pass ratio (passes / totalStudents) to totalPassRatio.
  • Compute the final average pass ratio by dividing totalPassRatio by the number of classes.

Step 6: Return the Result

  • Return the final computed average pass ratio as the output.

Dry Run

Input:

  • Classes: [[1,2], [3,5], [2,2]]
  • Extra Students: 2

Step 1: Initialize the Max Heap

  • Compute Initial Gains (Adding One Student to Each Class)
  • Class 0 ([1,2]): Gain = (2/3 - 1/2) ≈ 0.1667
  • Class 1 ([3,5]): Gain = (4/6 - 3/5) ≈ 0.0667
  • Class 2 ([2,2]): Gain = 0.0 (No improvement since it's already 1.0)
  • Push into Max Heap (maxHeap) (stored as negative gain for max heap behavior):
  • maxHeap = [(-0.1667, 1, 2), (-0.0667, 3, 5), (0.0, 2, 2)]

Step 2: Distribute Extra Students

  • First Extra Student (extraStudents = 2)
  • Extract max gain: Class 0 (Highest Gain = 0.1667)
  • Update Class 0 → [2,3]
  • Recalculate new gain for Class 0: (3/4 - 2/3) ≈ 0.0833
  • Push updated tuple back into maxHeap
  • New maxHeap = [(-0.0833, 2, 3), (-0.0667, 3, 5), (0.0, 2, 2)]
  • Decrement extraStudents → 1
  • Second Extra Student (extraStudents = 1)
  • Extract max gain: Class 0 again (Highest Gain = 0.0833)
  • Update Class 0 → [3,4]
  • Recalculate new gain for Class 0: (4/5 - 3/4) ≈ 0.05
  • Push updated tuple back into maxHeap
  • New maxHeap = [(-0.0667, 3, 5), (-0.05, 3, 4), (0.0, 2, 2)]
  • Decrement extraStudents → 0

Step 3: Compute Final Average Pass Ratio

  • Class 0 ([3,4]): 3/4 = 0.75
  • Class 1 ([3,5]): 3/5 = 0.6
  • Class 2 ([2,2]): 2/2 = 1.0
  • Sum of Pass Ratios: 0.75 + 0.6 + 1.0 = 2.35
  • Final Average Pass Ratio: 2.35 / 3 ≈ 0.78333

Final Output: 0.78333

Code for All Languages
C++ 
// Approach: Greedy Algorithm with Max Heap (Priority Queue)  
// Language: C++  
  
class Solution {  
public:  
    // Function to maximize the average pass ratio by distributing extra students optimally  
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {  
        // Step 1: Define a lambda function to calculate the gain in pass ratio  
        auto calculateGain = [](int passes, int totalStudents) {  
            return (double)(passes + 1) / (totalStudents + 1) -  
                   (double)passes / totalStudents;  
        };  

        // Step 2: Initialize a max heap (priority queue) to store (-gain, passes, totalStudents)  
        priority_queue<pair<double, pair<int, int>>> maxHeap;  
        for (const auto& singleClass : classes) {  
            maxHeap.push({calculateGain(singleClass[0], singleClass[1]),  
                          {singleClass[0], singleClass[1]}});  
        }  

        // Step 3: Distribute extra students one by one  
        while (extraStudents--) {  
            auto [currentGain, classInfo] = maxHeap.top();  
            maxHeap.pop();  

            int passes = classInfo.first;  
            int totalStudents = classInfo.second;  

            // Step 4: Add one student to the selected class and update the heap  
            maxHeap.push({calculateGain(passes + 1, totalStudents + 1),  
                          {passes + 1, totalStudents + 1}});  
        }  

        // Step 5: Compute the final average pass ratio  
        double totalPassRatio = 0;  
        while (!maxHeap.empty()) {  
            auto [_, classInfo] = maxHeap.top();  
            maxHeap.pop();  
            totalPassRatio += (double)classInfo.first / classInfo.second;  
        }  

        // Step 6: Return the average pass ratio across all classes  
        return totalPassRatio / classes.size();  
    }  
};

Java 
// Approach: Maximum Average Pass Ratio using Priority Queue  
// Language: Java  

class Solution {  

    // Function to maximize the average pass ratio by distributing extra students optimally  
    public double maxAverageRatio(int[][] classes, int extraStudents) {  
        // Priority queue to store classes based on the highest improvement potential  
        PriorityQueue<double[]> maxHeap = new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0]));

        // Step 1: Add all classes to the priority queue with their initial gain  
        for (int[] singleClass : classes) {  
            int passes = singleClass[0];  
            int totalStudents = singleClass[1];  
            double gain = calculateGain(passes, totalStudents);  
            maxHeap.offer(new double[] { gain, passes, totalStudents });  
        }  

        // Step 2: Distribute extra students one by one  
        while (extraStudents > 0) {  
            double[] current = maxHeap.poll();  
            int passes = (int) current[1];  
            int totalStudents = (int) current[2];  

            // Step 3: Add one student and update the heap  
            maxHeap.offer(new double[] { calculateGain(passes + 1, totalStudents + 1), passes + 1, totalStudents + 1 });  
            
            extraStudents--;  
        }  

        // Step 4: Compute the final average pass ratio  
        double totalPassRatio = 0;  
        while (!maxHeap.isEmpty()) {  
            double[] current = maxHeap.poll();  
            int passes = (int) current[1];  
            int totalStudents = (int) current[2];  
            totalPassRatio += (double) passes / totalStudents;  
        }  

        // Step 5: Return the average pass ratio across all classes  
        return totalPassRatio / classes.length;  
    }  

    // Function to calculate the gain of adding an extra student  
    private double calculateGain(int passes, int totalStudents) {  
        return ((double) (passes + 1) / (totalStudents + 1)) - ((double) passes / totalStudents);  
    }  
}

Python 
# Approach: Maximum Average Pass Ratio using Priority Queue  
# Language: Python  

import heapq  
from typing import List  

class Solution:  
    # Function to maximize the average pass ratio by distributing extra students optimally  
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:  
        # Lambda function to calculate the gain of adding an extra student  
        def _calculate_gain(passes, total_students):  
            return (passes + 1) / (total_students + 1) - passes / total_students  

        # Step 1: Max heap to store (-gain, passes, total_students)  
        max_heap = []  
        for passes, total_students in classes:  
            gain = _calculate_gain(passes, total_students)  
            heapq.heappush(max_heap, (-gain, passes, total_students))  

        # Step 2: Distribute extra students  
        for _ in range(extraStudents):  
            current_gain, passes, total_students = heapq.heappop(max_heap)  
            heapq.heappush(max_heap, (-_calculate_gain(passes + 1, total_students + 1), passes + 1, total_students + 1))  

        # Step 3: Compute the final average pass ratio  
        total_pass_ratio = sum(passes / total_students for _, passes, total_students in max_heap)  

        # Step 4: Return the average pass ratio across all classes  
        return total_pass_ratio / len(classes)

Javascript 
/** 
 * Approach: Maximum Average Pass Ratio using Priority Queue
 * Language: JavaScript
 *
 * @param {number[][]} classes - Array of classes where each class contains [pass, total] students.
 * @param {number} extraStudents - Number of extra students available to distribute.
 * @return {number} - Maximum possible average pass ratio.
 */
var maxAverageRatio = function(classes, extraStudents) {
    // Helper function to calculate the gain of adding an extra student
    const calculateGain = (pass, total) => {
        return (pass + 1) / (total + 1) - pass / total;
    };

    // Max heap (priority queue) sorted by maximum gain
    let maxHeap = new MaxPriorityQueue({ 
        priority: ([pass, total]) => calculateGain(pass, total) 
    });

    // Step 1: Push all classes into the max heap
    for (let [pass, total] of classes) {
        maxHeap.enqueue([pass, total]);
    }

    // Step 2: Distribute extra students
    while (extraStudents > 0) {
        let [pass, total] = maxHeap.dequeue().element;
        maxHeap.enqueue([pass + 1, total + 1]);  
        extraStudents--;
    }

    // Step 3: Compute the final average pass ratio
    let totalPassRatio = 0;
    while (!maxHeap.isEmpty()) {
        let [pass, total] = maxHeap.dequeue().element;
        totalPassRatio += pass / total;
    }

    // Step 4: Return the average pass ratio across all classes
    return totalPassRatio / classes.length;
};

Time Complexity Analysis: O(k .log(n) + n)

Heap Construction: O(n log n)

  • We insert n classes into a max heap.
  • Each insertion takes O(log n) time.
  • Thus, the total heap construction time is O(n log n).
  • Optimization Note: If we use heapify, the heap construction improves to O(n) instead of O(n log n).

Extra Students Distribution: O(k log n)

  • We distribute k extra students.
  • In each iteration:
    Extract the class with the highest gain (O(log n)).
    Update the pass and total count.
    Reinsert it into the heap (O(log n)).
  • Since this runs k times, the total complexity is O(k log n).

Final Pass Ratio Calculation: O(n)

  • We iterate through all n classes to compute the final average pass ratio.
  • This takes O(n) time.

Final Time Complexity: O(nlogn)+O(klogn)+O(n)=O(klogn+n)

Space Complexity Analysis: O(n)

Space Complexity Analysis: O(n)

Auxiliary Space Complexity: O(n)

  • We maintain a max heap storing n elements → O(n).
  • Other variables (like function parameters and counters) require only O(1) space.
  • Total Auxiliary Space Complexity: O(n).

Total Space Complexity: O(n)

  • The input array classes itself takes O(n) space.
  • The additional space used by the max heap is also O(n).

Final Space Complexity: O(n)+O(n)=O(n)

Similar Problems

Now we have successfully tackled this problem, let’s try these similar problems.

Maximum Subsequence Score

Given two integer arrays nums1 and nums2 of equal length n, and an integer k, select a subsequence of k indices from nums1.
The score of a chosen subsequence is defined as:
(sum of selected elements from nums1)×(minimum of selected elements from nums2)
Return the maximum possible score.

Minimum Operations to Reduce an Integer to 0

Given an array nums and an integer p, we need to form p pairs such that the maximum absolute difference among all pairs is minimized. Each index can be used only once. Sorting the array helps, and we can use binary search with a greedy approach to efficiently find the optimal minimum maximum difference.