Maximum Average Pass Ratio - Practice Coding Problems

Maximum Average Pass Ratio - Problem

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⁻⁵ of the actual answer will be accepted.

Input & Output

Example 1 — Basic Assignment

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

› Output: 0.78333

💡 Note: Initially: Class 1 has ratio 1/2=0.5, Class 2 has ratio 3/5=0.6. Adding one student to Class 1 gives (2,3) with ratio 2/3≈0.667. Adding another to Class 2 gives (4,6) with ratio 4/6≈0.667. Average = (0.667+0.667)/2 ≈ 0.667. Actually optimal is adding both to Class 1: (3,4) ratio = 0.75, (3,5) ratio = 0.6, average = 0.675.

Example 2 — Single Class

$ Input: classes = [[2,4]], extraStudents = 1

› Output: 0.6

💡 Note: Initially: Class has ratio 2/4 = 0.5. Adding one student gives (3,5) with ratio 3/5 = 0.6. Since there's only one class, the average is 0.6.

Example 3 — No Improvement Needed

$ Input: classes = [[3,3],[4,4]], extraStudents = 2

› Output: 1.0

💡 Note: Both classes already have 100% pass rate. Adding students maintains 100% pass rate: (4,4) and (5,5) both have ratio 1.0. Average remains 1.0.

Constraints

1 ≤ classes.length ≤ 10⁵
classes[i].length = 2
1 ≤ pass_i ≤ total_i ≤ 10⁵
1 ≤ extraStudents ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Classes

Each class has [pass_count, total_count] and current pass ratio

Distribute Students

Assign extra students to classes for maximum improvement

Final Average

Calculate the average of all class pass ratios

Key Takeaway

🎯 Key Insight: Always assign students to the class with maximum improvement potential using a greedy approach with priority queue

Asked in

G Google 28 f Facebook 15 a Amazon 12 M Microsoft 8

The key insight is that we should always assign each extra student to the class that gives the maximum improvement in pass ratio. Using a priority queue to track improvements leads to the optimal greedy solution. Best approach is Greedy with Priority Queue: Time: O(extraStudents × log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Priority Queue	O(extraStudents × log n)	O(n)	Always assign each extra student to the class with maximum improvement potential
Brute Force - Try All Distributions	O(n^extraStudents)	O(1)	Try every possible way to distribute extra students among classes

Greedy with Priority Queue — Algorithm Steps

Calculate improvement potential for each class
Use max-heap to always get class with highest improvement
Add one student to best class, recalculate improvement
Repeat until all extra students are assigned

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Max-Heap

Calculate improvement for each class and build heap

Assign Students

Always pick class with max improvement, update heap

Final Average

Calculate the final average pass ratio

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    double improvement;
    int index;
    int passCount;
    int totalCount;
} ClassInfo;

typedef struct {
    ClassInfo* data;
    int size;
    int capacity;
} MaxHeap;

MaxHeap* createHeap(int capacity) {
    MaxHeap* heap = malloc(sizeof(MaxHeap));
    heap->data = malloc(capacity * sizeof(ClassInfo));
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

void swap(ClassInfo* a, ClassInfo* b) {
    ClassInfo temp = *a;
    *a = *b;
    *b = temp;
}

void heapifyUp(MaxHeap* heap, int idx) {
    if (idx == 0) return;
    int parent = (idx - 1) / 2;
    if (heap->data[parent].improvement < heap->data[idx].improvement) {
        swap(&heap->data[parent], &heap->data[idx]);
        heapifyUp(heap, parent);
    }
}

void heapifyDown(MaxHeap* heap, int idx) {
    int largest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;
    
    if (left < heap->size && heap->data[left].improvement > heap->data[largest].improvement)
        largest = left;
    if (right < heap->size && heap->data[right].improvement > heap->data[largest].improvement)
        largest = right;
    
    if (largest != idx) {
        swap(&heap->data[idx], &heap->data[largest]);
        heapifyDown(heap, largest);
    }
}

void push(MaxHeap* heap, ClassInfo info) {
    heap->data[heap->size] = info;
    heapifyUp(heap, heap->size);
    heap->size++;
}

ClassInfo pop(MaxHeap* heap) {
    ClassInfo result = heap->data[0];
    heap->data[0] = heap->data[heap->size - 1];
    heap->size--;
    heapifyDown(heap, 0);
    return result;
}

double calculateImprovement(int passCount, int totalCount) {
    double currentRatio = (double) passCount / totalCount;
    double newRatio = (double) (passCount + 1) / (totalCount + 1);
    return newRatio - currentRatio;
}

double solution(int classes[][2], int n, int extraStudents) {
    MaxHeap* heap = createHeap(n);
    
    // Initialize heap
    for (int i = 0; i < n; i++) {
        double improve = calculateImprovement(classes[i][0], classes[i][1]);
        ClassInfo info = {improve, i, classes[i][0], classes[i][1]};
        push(heap, info);
    }
    
    // Assign extra students
    for (int j = 0; j < extraStudents; j++) {
        ClassInfo best = pop(heap);
        
        int newPass = best.passCount + 1;
        int newTotal = best.totalCount + 1;
        classes[best.index][0] = newPass;
        classes[best.index][1] = newTotal;
        
        double newImprove = calculateImprovement(newPass, newTotal);
        ClassInfo newInfo = {newImprove, best.index, newPass, newTotal};
        push(heap, newInfo);
    }
    
    // Calculate final average
    double totalRatio = 0;
    for (int i = 0; i < n; i++) {
        totalRatio += (double) classes[i][0] / classes[i][1];
    }
    
    free(heap->data);
    free(heap);
    
    return totalRatio / n;
}

int main() {
    int classes[2][2] = {{1, 2}, {3, 5}};
    int n = 2, extraStudents = 2;
    
    double result = solution(classes, n, extraStudents);
    printf("%f\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(extraStudents × log n)

For each of extraStudents, we extract max from heap and reinsert (log n operations)

⚡ Linearithmic

Space Complexity

O(n)

Priority queue stores one entry per class

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy with Priority Queue — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler