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.
In this approach, we directly use a sorting function and provide a custom comparator. This comparator sorts the 2D array (list of lists) based on the kth element of each row. Most programming languages have a built-in sort function that allows specifying custom comparison logic, either through a lambda function or similar constructs.
This approach leverages the power of built-in sorting functions that are generally well-optimized.
This C program sorts a 2D integer array based on the kth column using the qsort_r function, which enables passing additional arguments to the comparator. The comparator is designed to sort in descending order by comparing the kth elements of each row.
Time Complexity: O(m log m), where m is the number of students. Space Complexity: O(1) as the sorting is done in-place.
This approach uses a priority queue (or heap) to keep track of the highest scoring students based on the kth exam score. By building a max-heap based on the kth score, we efficiently retrieve students in the desired order. This approach is particularly valuable when we only need part of the sorted data.
This C++ solution uses a priority queue to store pairs of kth exam scores and student records. The max-heap allows us to extract students in descending order of their kth score. A vector is used to store the final sorted order of students.
Time Complexity: O(m log m), where m is the number of students due to heap operations. Space Complexity: O(m) due to the storage of the heap.
We directly sort score in descending order based on the scores in the k-th column, and then return the result.
The time complexity is O(m times log m), and the space complexity is O(log m). Here, m is the number of rows in score.
| Approach | Complexity |
|---|---|
| Direct Sorting Using Custom Comparator | Time Complexity: O(m log m), where m is the number of students. Space Complexity: O(1) as the sorting is done in-place. |
| Using a Priority Queue (Heap Approach) | Time Complexity: O(m log m), where m is the number of students due to heap operations. Space Complexity: O(m) due to the storage of the heap. |
| Sorting | — |
| 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 |
2545. Sort the Students by Their Kth Score | Weekly Contest 329 | LeetCode 2545 • Bro Coders • 2,209 views views
Watch 9 more video solutions →Practice Sort the Students by Their Kth Score with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor