2545. Sort the Students by Their Kth Score

Problem Description

In this problem, we have a class containing m students and n exams. We are presented with a matrix score of size m x n, where score[i][j] represents the score of the ith student in the jth exam. It's important to note that the scores are distinct, meaning no two students have received the exact same score in an exam.

We are also given an integer k, which refers to a specific exam. The task is to sort the students based on their scores in this kth exam. The sorting should be done in descending order - the student with the highest score on the kth exam should come first, and so on. What we aim to achieve is a new matrix with the same rows as the original score matrix, but ordered such that when looking at column k, the scores are in decreasing order.

Ultimately, we need to return the matrix once it has been sorted by these criteria.

Intuition

The solution to this problem is relatively straightforward due to Python's powerful sorting functions. We can use the built-in sorted function to sort the rows (students) based on their score in the kth exam (k is a 0-indexed exam number).

To specify the sorting criteria, we provide a lambda function to the key argument of sorted, which tells it to use the score at index k of each row as the key for sorting. Since we want to sort the scores in descending order, we negate the scores by using -x[k]. This means that higher scores will be treated as "smaller" by the sorting algorithm because of the negative sign, thereby placing them at the front of the sorted list.

This approach leverages Python's negative value ordering where it treats smaller values (negative values in this case) as having higher priority in the sort order, hence sorting the array in descending order based on the kth index.

So, the solution, in essence, is simply a one-liner that returns a new matrix score sorted by the score of the kth exam for each student, in descending order.

Learn more about Sorting patterns.

Solution Approach

The implementation is concise because it relies on Python's sorting algorithm, TimSort, an optimized hybrid sorting algorithm derived from merge sort and insertion sort. Here is a step-by-step breakdown:

1. The sorted function is called on the matrix score. In this case, score is a list of lists, with each inner list representing a student's scores across all exams.

2. The key parameter of the sorted function takes a lambda function. This lambda function lambda x: -x[k] is used to determine the sorting order. The key parameter defines the basis on which the elements of score are sorted. In this instance, the lambda returns the score of the kth exam (0-indexed) but negated, so high scores become lower numbers, and because Python sort is ascending by default, this negative transformation ensures that we get a descending order.

3. The inner workings of the sorted function then automatically handle the comparison of these keys (i.e., the negated kth exam scores) for each row in the matrix and arrange them in ascending order (which, due to the negation, corresponds to descending order of the actual scores).

4. As Python lists are 0-indexed, k refers directly to the correct column in the list of lists without requiring any adjustment.

5. The sorted list of lists, i.e., the sorted score matrix, is then returned as output. This new matrix has rows ordered by descending scores of the kth exam, which is exactly what the problem statement asked for.

Thus, the algorithm makes efficient use of Python's built-in sorting facilities and does not require any additional complex data structures or patterns. It's a simple, elegant solution that takes advantage of the way Python's sort works with keys and negation to achieve the desired descending order.

The full implementation in Python, as provided in the original solution, is as follows:

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

Example Walkthrough

Let's consider a small example to better understand the solution approach described above.

Suppose we have the following matrix score where m=3 (students) and n=4 (exams), and each cell score[i][j] represents the score of student i in exam j:

1score = [
2    [60, 85, 75, 90],  # Student 1
3    [88, 92, 67, 75],  # Student 2
4    [85, 85, 85, 88]   # Student 3
5]

We are also given k=2, which refers to the third exam (remember, indices start at 0).

Our goal is to sort the students based on their scores in the kth exam. So we need to look at the scores in exam 3:

1Exam 3 scores: [75, 67, 85]

We need to sort these scores in descending order and then rearrange the score matrix accordingly.

Now, using the solution approach:

1. We call the sorted function on the score matrix.
2. The key parameter is provided with a lambda function lambda x: -x[k]. Since k=2, the lambda function becomes lambda x: -x[2].
3. The sorted function applies this key (sorting criteria) to each student's list of exam scores.
4. Negative values are created for the scores of the third exam, which results in the following transformed scores: [-75, -67, -85].
5. These negative values are sorted in ascending order automatically by the sorted function, leading to the following order (while preserving the original scores): [-85, -75, -67].
6. This order corresponds to sorting the original scores of the third exam in descending order: [85, 75, 67].
7. Finally, the score matrix is reordered to match this sorting, giving us the following result:

1sorted_score = [
2    [85, 85, 85, 88],  # Student 3
3    [60, 85, 75, 90],  # Student 1
4    [88, 92, 67, 75]   # Student 2
5]

Here, if you look at the third column, which corresponds to exam 3, you'll see the scores are sorted in descending order: 85, 75, 67.

The code for this in Python, using the provided solution approach, would look like this:

1score = [
2    [60, 85, 75, 90],
3    [88, 92, 67, 75],
4    [85, 85, 85, 88]
5]
6k = 2
7
8sorted_score = sorted(score, key=lambda x: -x[k])
9print(sorted_score)

The output of this code snippet will be the sorted matrix:

1[[85, 85, 85, 88],
2 [60, 85, 75, 90],
3 [88, 92, 67, 75]]

As you can see, the students are now sorted by their scores in the third exam, in descending order, as required.

Solution Implementation

Time and Space Complexity

The time complexity of the provided sorting algorithm is O(n log n), where n is the number of items in the score list. This is because the built-in sorted function in Python uses an algorithm called Timsort, which has this time complexity on average.

The space complexity of the provided code is O(n), due to the space required to hold the new sorted list that is returned by the sorted function. The original list is not modified in place; instead, a new list is created to hold the sorted result.

Learn more about how to find time and space complexity quickly using problem constraints.