← Back to Heap Pattern

📚 Maximum Average Pass Ratio – Java Cheat Sheet

📌 What Is It?

The problem involves maximizing the average pass ratio of a set of classes after distributing a given number of extra students. Each class has a pass ratio defined as passed / total. Adding an extra student to a class increases its pass ratio, but the goal is to maximize the overall average pass ratio.

To solve this efficiently, we use a max-heap to prioritize classes where adding an extra student results in the largest increase in the pass ratio.

🧱 Pattern Template

class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        PriorityQueue<double[]> maxHeap = new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0]));

        // Step 1: Calculate the initial gain for each class and add to the heap
        for (int[] cls : classes) {
            int passed = cls[0], total = cls[1];
            double gain = gainIfAddStudent(passed, total);
            maxHeap.offer(new double[]{gain, passed, total});
        }

        // Step 2: Distribute extra students
        while (extraStudents > 0) {
            double[] top = maxHeap.poll();
            int passed = (int) top[1];
            int total = (int) top[2];
            passed++;
            total++;
            extraStudents--;
            double newGain = gainIfAddStudent(passed, total);
            maxHeap.offer(new double[]{newGain, passed, total});
        }

        // Step 3: Calculate the final average pass ratio
        double totalRatio = 0.0;
        while (!maxHeap.isEmpty()) {
            double[] cls = maxHeap.poll();
            totalRatio += cls[1] / cls[2];
        }

        return totalRatio / classes.length;
    }

    private double gainIfAddStudent(int passed, int total) {
        return ((double) (passed + 1) / (total + 1)) - ((double) passed / total);
    }
}

📊 Time Complexity

• Heap Initialization: O(n log n) – Adding all classes to the heap.
• Heap Operations: O(extraStudents × log n) – Distributing extra students involves heap operations.
• Overall Complexity: O((n + extraStudents) log n).

✅ Use Cases

• Maximizing averages in resource allocation problems
• Optimizing ratios or percentages with constraints
• Applications in education and performance metrics

📘 Common LeetCode Problems

• 1792. Maximum Average Pass Ratio [Medium] Heap

🧪 Example: Maximum Average Pass Ratio

Input: classes = [[1,2],[3,5],[2,2]], extraStudents = 2
Output: 0.78333

Explanation:
- Add one student to class [1,2], making it [2,3].
- Add one student to class [3,5], making it [4,6].
- Final pass ratios: [2/3, 4/6, 2/2].
- Average pass ratio = (2/3 + 4/6 + 2/2) / 3 = 0.78333.

▶️ View Animation

💡 Pro Tips

• Use a max-heap to prioritize classes with the largest potential gain in pass ratio.
• Edge cases: no extra students, all classes with the same pass ratio.
• Ensure calculations are precise to avoid floating-point errors.