#2545

Medium

LeetCode Problem Workspace

Sort the Students by Their Kth Score

Sort a matrix of student scores by the kth exam efficiently using array manipulation and custom sorting techniques.

Problem Statement

You are given an m x n integer matrix representing scores of m students across n exams. Each row corresponds to one student, and score[i][j] is the score of the ith student in the jth exam. All scores are distinct.

Given an integer k, sort the students by their kth exam score in descending order. Return the sorted matrix with each row representing a student in the new order based on the kth score.

Examples

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]]

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]]

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.length
n == score[i].length
1 <= m, n <= 250
1 <= score[i][j] <= 105
score consists of distinct integers.
0 <= k < n

Solution Approach

Direct Sorting by Kth Score

Use a sorting algorithm that takes a comparator based on the kth column. This allows the matrix rows to be rearranged according to the kth exam score directly, ensuring descending order.

Custom Key Function

Implement a key function that extracts the kth score for each row. Feed this key into the sort routine so that the rows are automatically ordered without additional swaps or iterations.

In-Place Sorting Optimization

For large matrices, perform the sort in-place to reduce memory usage. Swap rows directly based on kth scores while iterating, minimizing overhead and maintaining array integrity.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting requires O(m log m) time due to row comparisons based on the kth column. Space complexity is O(1) if sorted in-place or O(m) if using auxiliary arrays for sorting.

What Interviewers Usually Probe

Will check if you can sort rows based on a specific column rather than the whole row.
Expect awareness of descending order priority and how to preserve row structure.
May ask about in-place vs auxiliary space trade-offs for large matrices.

Common Pitfalls or Variants

Common pitfalls

Sorting the entire row instead of comparing only the kth element.
Accidentally reversing the order, giving ascending results instead of descending.
Using extra space unnecessarily when an in-place sort suffices for m x n matrix.

Follow-up variants

Sort students by multiple exam scores, using primary, secondary sorting keys.
Handle matrices with duplicate scores in the kth exam, requiring stable sorting.
Sort columns instead of rows to rank exams rather than students.

FAQ

How do I sort the students by their kth score?

Use a sort function that compares the kth element of each row and arranges rows in descending order.

Can I sort this matrix in-place?

Yes, swapping rows based on their kth score allows in-place sorting, saving extra memory.

What happens if two students have the same kth score?

Since the problem states all scores are distinct, this situation does not occur; otherwise, a stable sort would preserve original order.

Does this relate to any common array patterns?

Yes, this is an array plus sorting pattern where sorting depends on a specific column rather than the whole row.

What is the best approach for large matrices?

Use an efficient in-place sort with a custom comparator on the kth score to minimize both time and space complexity.

terminal

Solution

Solution 1: Sorting

We directly sort $\textit{score}$ in descending order based on the scores in the $k$-th column, and then return the result.

1

2

3

class Solution:
    def sortTheStudents(self, score: List[List[int]], k: int) -> List[List[int]]:
        return sorted(score, key=lambda x: -x[k])

Continue Practicing

#2503 maximum number of points from grid queries #2500 delete greatest value in each row #2679 sum in a matrix