Sort the Students by Their Kth Score
MedPrompt
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] <= 105scoreconsists of distinct integers.0 <= k < n
Approaches
4 approaches with complexity analysis and trade-offs.
This approach uses a simple, elementary sorting algorithm like Bubble Sort to reorder the rows of the matrix. It repeatedly steps through the list of students, compares the k-th score of adjacent students, and swaps their entire rows if they are in the wrong order. This method is straightforward but not efficient.
Algorithm
- Iterate through the students from
i = 0tom-2. - In a nested loop, iterate from
j = 0tom-i-2. - Compare the k-th score of student
j(score[j][k]) with the k-th score of studentj+1(score[j+1][k]). - If
score[j][k] < score[j+1][k], it means studentj+1has a higher score and should come before studentj. Swap the entire rowsscore[j]andscore[j+1]. - A temporary array of size
nis needed to perform the swap. - After the loops complete, the
scorematrix will be sorted in descending order based on the k-th exam.
Walkthrough
The algorithm works by comparing each pair of adjacent rows based on their scores in the k-th column. If a pair is found to be in the wrong order (i.e., the student with the lower score is ahead of the student with the higher score), their entire rows are swapped. This process is repeated m times, with each pass 'bubbling up' the student with the next highest score to their correct position. A temporary array of size n is used to facilitate the swapping of two rows.
class Solution { public int[][] sortTheStudents(int[][] score, int k) { int m = score.length; int n = score[0].length; for (int i = 0; i < m; i++) { for (int j = 0; j < m - 1 - i; j++) { if (score[j][k] < score[j + 1][k]) { // Swap the entire rows int[] temp = score[j]; score[j] = score[j + 1]; score[j + 1] = temp; } } } return score; }}Complexity
Time
O(m² * n). The two nested loops for comparison run in O(m²) time. Inside the inner loop, swapping two rows of length `n` takes O(n) time. Thus, the total time complexity is O(m² * n).
Space
O(n). We need an auxiliary array of size `n` to temporarily hold a row during the swap operation.
Trade-offs
Pros
Simple to understand and implement from scratch without relying on built-in libraries.
Cons
Highly inefficient due to its quadratic time complexity.
Will be very slow for larger
mand may lead to a 'Time Limit Exceeded' error on coding platforms.
Solutions
Solution
class Solution {public int[][] sortTheStudents(int[][] score, int k) { Arrays.sort(score, (a, b)->b[k] - a[k]); return score; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.