High Five - Practice Coding Problems

High Five - Problem

Given a list of the scores of different students, items, where items[i] = [IDi, scorei] represents one score from a student with IDi, calculate each student's top five average.

Return the answer as an array of pairs result, where result[j] = [IDj, topFiveAveragej] represents the student with IDj and their top five average. Sort result by IDj in increasing order.

A student's top five average is calculated by taking the sum of their top five scores and dividing it by 5 using integer division.

Input & Output

Example 1 — Basic Case

$ Input: items = [[1,91],[1,92],[2,93],[2,97],[1,60],[2,77],[1,65],[1,87],[1,100],[2,100],[2,76]]

› Output: [[1,87],[2,88]]

💡 Note: Student 1 has scores [91,92,60,65,87,100]. Top 5 are [100,92,91,87,65], average = (100+92+91+87+65)/5 = 87. Student 2 has scores [93,97,77,100,76]. Top 5 are [100,97,93,77,76], average = (100+97+93+77+76)/5 = 88.

Example 2 — Minimum Scores

$ Input: items = [[1,100],[1,90],[1,80],[2,85],[2,95]]

› Output: [[1,90],[2,90]]

💡 Note: Student 1 has only 3 scores [100,90,80], so we pad with zeros: (100+90+80+0+0)/5 = 54. Student 2 has only 2 scores [85,95], so we pad: (95+85+0+0+0)/5 = 36.

Example 3 — Single Student

$ Input: items = [[1,70],[1,80],[1,90],[1,85],[1,95],[1,75]]

› Output: [[1,85]]

💡 Note: Student 1 has 6 scores [70,80,90,85,95,75]. Top 5 are [95,90,85,80,75], average = (95+90+85+80+75)/5 = 85.

Constraints

1 ≤ items.length ≤ 1000
items[i].length == 2
1 ≤ ID_i ≤ 1000
0 ≤ score_i ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

List of [studentID, score] pairs from different students

Process

Group by student ID and find top 5 scores for each

Output

Array of [studentID, topFiveAverage] sorted by ID

Key Takeaway

🎯 Key Insight: Group scores by student ID first, then efficiently maintain only the top 5 scores using a hash map and sorting or heap data structure.

Asked in

G Google 12 a Amazon 8 f Facebook 6

The key insight is to group student scores by ID first, then efficiently find the top 5 scores for each student. The hash map approach with min-heap optimization provides the best balance of simplicity and efficiency. Time: O(n log 5 + k log k), Space: O(k × 5).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map with Partial Sorting	O(n log 5 + k log k)	O(k × 5)	Use hash map to group, then sort only the top scores efficiently
Brute Force with Sorting	O(n × m log m)	O(n × m)	Group scores by student ID, sort each student's scores, take top 5

Hash Map with Partial Sorting — Algorithm Steps

Use hash map to group scores by ID
For each score, maintain top 5 list
Sort final results by student ID
Calculate averages

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Scores

For each score, maintain top 5 using min-heap

Heap Maintenance

If heap size < 5, add score. If score > min, replace min

Calculate Result

Sum heap contents and compute average

Code -

solution.c — C

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

#define MAX_STUDENTS 1000
#define TOP_SCORES 5

struct StudentScore {
    int id;
    int scores[TOP_SCORES];
    int count;
};

// Min heap operations for maintaining top 5 scores
void heapifyUp(int* heap, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (heap[parent] <= heap[index]) break;
        int temp = heap[parent];
        heap[parent] = heap[index];
        heap[index] = temp;
        index = parent;
    }
}

void heapifyDown(int* heap, int size, int index) {
    while (1) {
        int smallest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        
        if (left < size && heap[left] < heap[smallest]) smallest = left;
        if (right < size && heap[right] < heap[smallest]) smallest = right;
        
        if (smallest == index) break;
        int temp = heap[index];
        heap[index] = heap[smallest];
        heap[smallest] = temp;
        index = smallest;
    }
}

void insertScore(struct StudentScore* student, int score) {
    if (student->count < TOP_SCORES) {
        student->scores[student->count] = score;
        heapifyUp(student->scores, student->count);
        student->count++;
    } else if (score > student->scores[0]) {
        student->scores[0] = score;
        heapifyDown(student->scores, TOP_SCORES, 0);
    }
}

int compareStudents(const void* a, const void* b) {
    return ((struct StudentScore*)a)->id - ((struct StudentScore*)b)->id;
}

int** solution(int** items, int itemsSize, int* itemsColSize, int* returnSize, int** returnColumnSizes) {
    struct StudentScore students[MAX_STUDENTS];
    int studentCount = 0;
    
    // Group scores by student ID
    for (int i = 0; i < itemsSize; i++) {
        int studentId = items[i][0];
        int score = items[i][1];
        
        // Find or create student
        int found = -1;
        for (int j = 0; j < studentCount; j++) {
            if (students[j].id == studentId) {
                found = j;
                break;
            }
        }
        
        if (found == -1) {
            students[studentCount].id = studentId;
            students[studentCount].count = 0;
            found = studentCount++;
        }
        
        insertScore(&students[found], score);
    }
    
    // Sort students by ID
    qsort(students, studentCount, sizeof(struct StudentScore), compareStudents);
    
    // Calculate results
    int** result = malloc(sizeof(int*) * studentCount);
    *returnColumnSizes = malloc(sizeof(int) * studentCount);
    
    for (int i = 0; i < studentCount; i++) {
        int sum = 0;
        int count = students[i].count;
        
        // Sum all scores (pad with 0s if less than 5)
        for (int j = 0; j < TOP_SCORES; j++) {
            if (j < count) {
                sum += students[i].scores[j];
            }
        }
        
        int average = sum / TOP_SCORES;
        
        result[i] = malloc(sizeof(int) * 2);
        result[i][0] = students[i].id;
        result[i][1] = average;
        (*returnColumnSizes)[i] = 2;
    }
    
    *returnSize = studentCount;
    return result;
}

int main() {
    int items[100][2];
    int itemsSize = 0;
    
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse input
    char* ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            items[itemsSize][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            items[itemsSize][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            itemsSize++;
        }
        ptr++;
    }
    
    int** itemPtrs = malloc(sizeof(int*) * itemsSize);
    int* colSizes = malloc(sizeof(int) * itemsSize);
    for (int i = 0; i < itemsSize; i++) {
        itemPtrs[i] = items[i];
        colSizes[i] = 2;
    }
    
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(itemPtrs, itemsSize, colSizes, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[%d,%d]", result[i][0], result[i][1]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    // Cleanup
    for (int i = 0; i < returnSize; i++) {
        free(result[i]);
    }
    free(result);
    free(returnColumnSizes);
    free(itemPtrs);
    free(colSizes);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log 5 + k log k)

n items each taking O(log 5) to maintain top 5, plus O(k log k) to sort k students

⚡ Linearithmic

Space Complexity

O(k × 5)

Hash map stores at most 5 scores per student, k students total

✓ Linear Space

18.5K Views

Medium Frequency

~15 min Avg. Time

542 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

Hash Map with Partial Sorting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler