LeetCode 2545 - Sort the Students by Their Kth Score

LeetCode Problem 2545

Difficulty: 🟡 Medium
Topics: Array, Sorting, Matrix

Solution

Problem Understanding

In this problem, we are given a matrix named score with dimensions m x n. Each row represents a student, and each column represents an exam. The value score[i][j] is the score obtained by the ith student on the jth exam.

The task is to sort the rows of the matrix according to the values in a specific column k. The sorting must be performed in descending order, meaning the student with the highest score in exam k should appear first, and the student with the lowest score in that exam should appear last.

The important detail is that we are not sorting individual values inside rows. Instead, we are rearranging entire rows based on the value located at index k within each row.

For example, if k = 2, then we compare score[i][2] for every student and sort the rows according to those values.

The constraints are relatively small:

• The number of students m can be at most 250.
• The number of exams n can also be at most 250.
• All values inside the matrix are distinct.

These constraints immediately suggest that standard sorting algorithms are more than fast enough. Even an O(m log m) sorting solution is trivial for m = 250.

The guarantee that all integers are distinct is important because it means there are no ties when comparing the kth scores. Every student will have a unique ranking for the selected exam.

There are several edge cases worth considering:

• A matrix with only one student. Sorting should leave the matrix unchanged.
• A matrix with only one exam. Sorting then becomes equivalent to sorting rows by their single value.
• The selected column k may be the first column or the last column.
• The rows may already be sorted in descending order.
• The rows may be sorted in ascending order, requiring a complete reversal.

A naive implementation could accidentally sort the values within each row instead of sorting the rows themselves. Another common mistake is sorting in ascending order instead of descending order.

Approaches

Brute Force Approach

A straightforward approach is to manually perform a sorting algorithm such as bubble sort on the rows of the matrix.

In this method, we repeatedly compare adjacent rows using their kth score. If the current row has a smaller kth score than the next row, we swap the two rows. Repeating this process eventually places the rows in descending order.

This approach is correct because comparison-based sorting guarantees that rows will eventually be ordered according to the desired column. However, bubble sort performs many unnecessary comparisons and swaps.

Since bubble sort requires O(m^2) comparisons in the worst case, it is less efficient than using the language's built-in optimized sorting implementation.

Optimal Approach

The key observation is that we only need to sort the rows according to one specific column value.

Modern programming languages already provide highly optimized sorting functions. We can directly sort the rows using the value at index k as the sorting key.

In Python, this can be done using:

sorted(score, key=lambda row: row[k], reverse=True)

In Go, we can use sort.Slice with a custom comparison function.

This approach is both simpler and more efficient than implementing a manual sorting algorithm.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m²)	O(1)	Uses manual bubble sort on rows
Optimal	O(m log m)	O(1) or O(m) depending on implementation	Uses built-in optimized sorting

Algorithm Walkthrough

1. Read the input matrix score and the column index k.
2. Treat each row as a single unit representing one student. We never modify values inside a row.
3. Compare rows using the value located at index k. For two rows a and b, compare a[k] and b[k].
4. Sort all rows in descending order according to these kth values. Descending order is required because students with higher scores should appear earlier.
5. Return the reordered matrix after sorting completes.

Why it works

The algorithm works because every row is compared using exactly the score specified by column k. A comparison-based sorting algorithm guarantees that after sorting, for every adjacent pair of rows i and i + 1, we have:

score[i][k] >= score[i + 1][k]

Since all rows satisfy this ordering condition, the entire matrix is correctly sorted by the kth exam score from highest to lowest.

Python Solution

from typing import List

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

The implementation is very concise because Python provides a powerful built-in sorting function.

The sorted() function creates a new sorted list. The key argument specifies how rows should be compared. For each row, we extract row[k], which represents the student's score in the target exam.

The argument reverse=True ensures descending order.

Because rows themselves are lists, sorting rearranges entire rows rather than individual values.

The algorithm directly follows the approach described earlier:

• Each row is treated as a student record.
• The kth value becomes the comparison key.
• The rows are reordered according to that key.

Go Solution

package main

import "sort"

func sortTheStudents(score [][]int, k int) [][]int {
	sort.Slice(score, func(i, j int) bool {
		return score[i][k] > score[j][k]
	})

	return score
}

In Go, sorting is performed in place using sort.Slice.

The comparison function receives indices i and j. We compare the kth score of the two rows:

score[i][k] > score[j][k]

Using > instead of < ensures descending order.

Unlike Python's sorted(), which returns a new list, sort.Slice modifies the original slice directly.

Go slices are references to underlying arrays, so the rows themselves are rearranged without copying every element individually.

Worked Examples

Example 1

Input:

score = [
    [10, 6, 9, 1],
    [7, 5, 11, 2],
    [4, 8, 3, 15]
]

k = 2

We compare rows using column index 2.

Student Row	Value at Index 2
[10, 6, 9, 1]	9
[7, 5, 11, 2]	11
[4, 8, 3, 15]	3

Now sort these values in descending order:

11 > 9 > 3

So the rows become:

Position	Row
1st	[7, 5, 11, 2]
2nd	[10, 6, 9, 1]
3rd	[4, 8, 3, 15]

Final output:

[
    [7, 5, 11, 2],
    [10, 6, 9, 1],
    [4, 8, 3, 15]
]

Example 2

Input:

score = [
    [3, 4],
    [5, 6]
]

k = 0

We compare rows using column index 0.

Student Row	Value at Index 0
[3, 4]	3
[5, 6]	5

Descending order:

5 > 3

Reordered rows:

Position	Row
1st	[5, 6]
2nd	[3, 4]

Final output:

[
    [5, 6],
    [3, 4]
]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m log m)	Sorting m rows requires comparison-based sorting
Space	O(1) to O(m)	Depends on language sorting implementation

The dominant operation is sorting the rows. Since there are m students, sorting requires O(m log m) comparisons.

Each comparison only checks a single integer at index k, so comparisons are constant time.

The space complexity depends on the language implementation. Go's in-place sorting uses very little extra memory, while Python's sorted() creates a new list structure.

Test Cases

from typing import List

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

s = Solution()

# Example 1
assert s.sortTheStudents(
    [[10,6,9,1],[7,5,11,2],[4,8,3,15]],
    2
) == [[7,5,11,2],[10,6,9,1],[4,8,3,15]]  # basic example

# Example 2
assert s.sortTheStudents(
    [[3,4],[5,6]],
    0
) == [[5,6],[3,4]]  # two-row matrix

# Single student
assert s.sortTheStudents(
    [[1,2,3]],
    1
) == [[1,2,3]]  # no reordering needed

# Single exam column
assert s.sortTheStudents(
    [[5],[2],[9]],
    0
) == [[9],[5],[2]]  # sorting by only column

# Already sorted descending
assert s.sortTheStudents(
    [[9,1],[7,2],[5,3]],
    0
) == [[9,1],[7,2],[5,3]]  # remains unchanged

# Sorted ascending originally
assert s.sortTheStudents(
    [[1,9],[3,7],[5,5]],
    0
) == [[5,5],[3,7],[1,9]]  # requires reversal

# Sorting by last column
assert s.sortTheStudents(
    [[1,100],[2,50],[3,75]],
    1
) == [[1,100],[3,75],[2,50]]  # uses last index

# Maximum-style distinct ordering
assert s.sortTheStudents(
    [[1000,1],[999,2],[998,3]],
    0
) == [[1000,1],[999,2],[998,3]]  # large values

# Larger matrix
assert s.sortTheStudents(
    [
        [1,2,3],
        [7,8,9],
        [4,5,6],
        [10,11,12]
    ],
    1
) == [
    [10,11,12],
    [7,8,9],
    [4,5,6],
    [1,2,3]
]  # multiple rows

Test	Why
Example 1	Verifies standard sorting behavior
Example 2	Verifies simple two-row input
Single student	Ensures trivial case works
Single exam column	Tests one-dimensional behavior
Already sorted descending	Ensures no unnecessary changes
Originally ascending	Tests full reordering
Sorting by last column	Verifies column indexing
Large values	Confirms value magnitude does not matter
Larger matrix	Tests multiple rows and columns

Edge Cases

One important edge case is when the matrix contains only a single student. In that situation, there is nothing to sort because only one row exists. Some incorrect implementations may still attempt unnecessary swaps or comparisons. The provided solution handles this naturally because sorting a single-element list simply returns the same list unchanged.

Another important edge case is when there is only one exam column. In this case, k must be 0, and sorting is based entirely on the single value in each row. A buggy implementation might incorrectly assume multiple columns exist. Since the algorithm directly accesses row[k], it works correctly even when each row contains only one element.

A third edge case occurs when the matrix is already sorted in descending order. Some manual sorting implementations accidentally destabilize or corrupt already ordered data because of incorrect swap logic. Using the language's built-in sorting mechanism guarantees correct ordering without introducing unnecessary modifications.

Another subtle edge case is sorting by the last column index. Off-by-one indexing errors are common when dealing with matrix columns. Since the solution always uses the exact index k supplied by the problem and the constraints guarantee 0 <= k < n, the implementation safely handles both the first and last columns.