Code Implementation

from collections import defaultdict

def highestGrades(grades):
    # grades: List[List[int]] where each element is [student_id, grade]
    best = defaultdict(int)
    for student_id, grade in grades:
        if student_id not in best or grade > best[student_id]:
            best[student_id] = grade
    # Return as list of [student_id, highest_grade], sorted by student_id
    return sorted([[sid, grd] for sid, grd in best.items()])
      

#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<vector<int>> highestGrades(vector<vector<int>>& grades) {
    unordered_map<int, int> best;
    for (const auto& rec : grades) {
        int id = rec[0], grade = rec[1];
        if (best.find(id) == best.end() || grade > best[id]) {
            best[id] = grade;
        }
    }
    vector<vector<int>> result;
    for (const auto& p : best) {
        result.push_back({p.first, p.second});
    }
    sort(result.begin(), result.end());
    return result;
}
      

import java.util.*;

public class Solution {
    public List<List<Integer>> highestGrades(int[][] grades) {
        Map<Integer, Integer> best = new HashMap<>();
        for (int[] rec : grades) {
            int id = rec[0], grade = rec[1];
            if (!best.containsKey(id) || grade > best.get(id)) {
                best.put(id, grade);
            }
        }
        List<List<Integer>> result = new ArrayList<>();
        for (int id : best.keySet()) {
            result.add(Arrays.asList(id, best.get(id)));
        }
        result.sort(Comparator.comparingInt(a -> a.get(0)));
        return result;
    }
}
      

function highestGrades(grades) {
    // grades: Array of [student_id, grade]
    const best = {};
    for (const [id, grade] of grades) {
        if (!(id in best) || grade > best[id]) {
            best[id] = grade;
        }
    }
    // Convert to array and sort by student_id
    return Object.entries(best)
        .map(([id, grade]) => [parseInt(id), grade])
        .sort((a, b) => a[0] - b[0]);
}
      

Problem Description

You are given a list of student grades, where each grade is represented as a pair [student_id, grade]. Each student may have multiple grades. Your task is to determine the highest grade for each student and return a list of pairs [student_id, highest_grade] sorted by student_id.

Constraints:

• Each student_id is unique in the output.
• Do not reuse elements; each grade belongs to one student.
• There is exactly one highest grade per student.

Thought Process

The problem asks for the highest grade per student from a list of grade records. At first glance, you might consider comparing each student's grades to all others, but this would be inefficient. Instead, we can keep track of the highest grade we've seen so far for each student as we iterate through the list. This way, we only need to look at each record once, updating our result as we go.

The key insight is that we only care about the maximum grade for each student, not the full list. Using a data structure that allows for quick updates and lookups by student_id (like a hash map or dictionary) makes this efficient.

Solution Approach

• Step 1: Create a hash map (or dictionary) to store the highest grade for each student_id.
• Step 2: Iterate over each grade record in the input list.
• Step 3: For each record, check if the student_id is already in the map:
  • If not, add it with the current grade.
  • If yes, compare the stored grade and the current grade, and keep the higher one.
• Step 4: After processing all records, collect the [student_id, highest_grade] pairs from the map.
• Step 5: Sort the result list by student_id (since the output must be ordered).
• Step 6: Return the sorted list.

We use a hash map because it allows us to look up and update each student's best grade in constant time. Sorting at the end ensures the output meets the required format.

Example Walkthrough

Suppose the input is: grades = [[1, 91], [2, 93], [1, 92], [2, 97], [3, 90]]

• Start with an empty map: {}
• Process [1, 91]: map becomes {1: 91}
• Process [2, 93]: map becomes {1: 91, 2: 93}
• Process [1, 92]: compare 92 with 91, update to {1: 92, 2: 93}
• Process [2, 97]: compare 97 with 93, update to {1: 92, 2: 97}
• Process [3, 90]: add 3: 90, final map is {1: 92, 2: 97, 3: 90}

We then sort the pairs by student_id to get [[1, 92], [2, 97], [3, 90]].

Time and Space Complexity

Brute-force approach: For each student, scan the entire list to find their highest grade. If there are n records and m students, this is O(mn).

Optimized approach: Using a hash map:

• We process each record once: O(n).
• Building the output list: O(m).
• Sorting by student_id: O(m \log m).
• Total time: O(n + m \log m).
• Space: O(m) for the hash map and output.

Summary

The problem is efficiently solved by using a hash map to track the highest grade per student as we process the input. This avoids redundant comparisons and leverages fast dictionary operations. Sorting at the end ensures the output is in the correct order. The approach is both simple and optimal for time and space, making it a solid example of using the right data structure for the job.