Watch 10 video solutions for Sort the Students by Their Kth Score, a medium level problem involving Array, Sorting, Matrix. This walkthrough by Bro Coders has 2,209 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There is a class with m students and n exams. You are given a 0-indexed m x n integer matrix score, where each row represents one student and score[i][j] denotes the score the ith student got in the jth exam. The matrix score contains distinct integers only.
You are also given an integer k. Sort the students (i.e., the rows of the matrix) by their scores in the kth (0-indexed) exam from the highest to the lowest.
Return the matrix after sorting it.
Example 1:
Input: score = [[10,6,9,1],[7,5,11,2],[4,8,3,15]], k = 2 Output: [[7,5,11,2],[10,6,9,1],[4,8,3,15]] Explanation: In the above diagram, S denotes the student, while E denotes the exam. - The student with index 1 scored 11 in exam 2, which is the highest score, so they got first place. - The student with index 0 scored 9 in exam 2, which is the second highest score, so they got second place. - The student with index 2 scored 3 in exam 2, which is the lowest score, so they got third place.
Example 2:
Input: score = [[3,4],[5,6]], k = 0 Output: [[5,6],[3,4]] Explanation: In the above diagram, S denotes the student, while E denotes the exam. - The student with index 1 scored 5 in exam 0, which is the highest score, so they got first place. - The student with index 0 scored 3 in exam 0, which is the lowest score, so they got second place.
Constraints:
m == score.lengthn == score[i].length1 <= m, n <= 2501 <= score[i][j] <= 105score consists of distinct integers.0 <= k < nProblem Overview: You are given a matrix where each row represents a student and each column represents a score in a particular exam. The task is to sort all students in descending order based on their score in the kth column while keeping each student's full score row intact.
Approach 1: Direct Sorting Using Custom Comparator (O(n log n) time, O(1) extra space)
The most straightforward solution sorts the matrix rows using the value at column k as the sorting key. Use the built‑in sorting function and provide a custom comparator (or key function) that compares row[k]. Since sorting algorithms typically run in O(n log n) for n students, the overall runtime follows the same complexity. No additional data structures are required beyond the sorting stack, so auxiliary space is O(1) or O(log n) depending on the language implementation. This approach is concise and leverages optimized standard library sorting.
Approach 2: Using a Priority Queue (Heap Approach) (O(n log n) time, O(n) space)
Another option pushes each student row into a max‑heap keyed by the kth score. Each heap node stores the full row so the matrix structure remains intact. Building the heap takes O(n) time, and extracting all students in sorted order requires n pop operations, each costing O(log n). The resulting rows are collected in descending order of the kth score. This method uses O(n) additional space for the heap but provides flexibility when you need partial ordering or top‑k extraction.
The problem mainly tests familiarity with array manipulation and built‑in sorting utilities while handling a 2D matrix structure. The key insight is that the sorting key is a single column value, but the entire row must move together during reordering.
Recommended for interviews: Direct sorting with a custom comparator. It is the most idiomatic solution and clearly shows you understand how to sort structured data by a specific key. Mentioning the heap approach demonstrates awareness of alternative ordering techniques, but interviewers typically expect the comparator‑based sort.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Sorting Using Custom Comparator | O(n log n) | O(1) or O(log n) | Best general solution when you need the entire matrix sorted by the kth column |
| Priority Queue (Heap) | O(n log n) | O(n) | Useful when you already use a heap or when extracting top‑k rows instead of fully sorting |