# Sort the Students by Their Kth Score
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sort-the-students-by-their-kth-score)
Canonical: https://scaleengineer.com/dsa/problems/sort-the-students-by-their-kth-score
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Matrix
**Companies:** [IBM](https://scaleengineer.com/companies/ibm)
---
## Problem
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:**

![](https://assets.glich.co/dsa/sort-the-students-by-their-kth-score/image0.png) 

**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:**

![](https://assets.glich.co/dsa/sort-the-students-by-their-kth-score/image1.png) 

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

# Approaches
## Brute-Force with Bubble Sort
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.
**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.
**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 `m` and may lead to a 'Time Limit Exceeded' error on coding platforms.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
*   Iterate through the students from `i = 0` to `m-2`.
*   In a nested loop, iterate from `j = 0` to `m-i-2`.
*   Compare the k-th score of student `j` (`score[j][k]`) with the k-th score of student `j+1` (`score[j+1][k]`).
*   If `score[j][k] < score[j+1][k]`, it means student `j+1` has a higher score and should come before student `j`. Swap the entire rows `score[j]` and `score[j+1]`.
*   A temporary array of size `n` is needed to perform the swap.
*   After the loops complete, the `score` matrix will be sorted in descending order based on the k-th exam.

## Using Counting Sort
This approach leverages the fact that the scores are integers within a known range. Counting sort is a non-comparison-based algorithm that can sort in linear time with respect to the range of values. Here, we adapt the principle by creating a map (using an array) from a score to the student's row. We then iterate through the possible scores from highest to lowest to construct the sorted matrix.
**Time:** O(m*n + S). Finding the max score takes O(m). Populating the map takes O(m). Building the final sorted matrix takes O(S + m*n) because we iterate through all possible scores and copy `m` rows of length `n`. · **Space:** O(m*n + S). We need `O(S)` space for the `scoreToRowMap` array (where S is the max score) and `O(m*n)` space for the new `sortedScore` matrix.
**Pros:** Can be faster than comparison-based sorts if the range of scores `S` is small.; Avoids the complexities of comparison logic.
**Cons:** Uses a large amount of extra space, proportional to the maximum score, which can be very large (`10^5`).; The time complexity is dependent on the range of scores, which can be less efficient if the range is very large compared to `m log m`.
### Explanation
Since the scores are positive integers up to `10^5`, we can use an array as a direct-address table to map scores to rows. First, we find the maximum score in the `k`-th column to size our mapping array appropriately. Then, we populate this map. Finally, we construct the sorted result matrix by iterating through our map from the highest possible score down to the lowest, adding the corresponding rows to our result.

```java
class Solution {
    public int[][] sortTheStudents(int[][] score, int k) {
        int m = score.length;
        int n = score[0].length;
        int maxScore = 0;
        for (int i = 0; i < m; i++) {
            maxScore = Math.max(maxScore, score[i][k]);
        }

        // Map scores to rows. Using an array of int[] since scores are distinct.
        int[][] scoreToRowMap = new int[maxScore + 1][];
        for (int i = 0; i < m; i++) {
            scoreToRowMap[score[i][k]] = score[i];
        }

        int[][] sortedScore = new int[m][n];
        int index = 0;
        // Iterate from highest score to lowest
        for (int s = maxScore; s >= 0; s--) {
            if (scoreToRowMap[s] != null) {
                sortedScore[index] = scoreToRowMap[s];
                index++;
            }
        }
        return sortedScore;
    }
}
```
### Algorithm
*   Determine the maximum possible score, `S`, in the `k`-th column (or use the constraint `10^5`).
*   Create a data structure to map each score to its corresponding row. An array `scoreToRowMap` of size `S+1` can be used, where the index represents the score.
*   Iterate through the input `score` matrix. For each row `i`, store the row `score[i]` at index `score[i][k]` in `scoreToRowMap`.
*   Create a new result matrix `result` of size `m x n`.
*   Iterate from the maximum score `S` down to `0`. For each score `s`, if a row is mapped to it, copy that row into the `result` matrix.
*   Return the `result` matrix.

## Sorting with a TreeMap
This approach uses a `TreeMap`, a sorted map implementation based on a Red-Black Tree. We can use the k-th score as the key and the entire student row as the value. The `TreeMap` will automatically keep the entries sorted by the key. We can then iterate through the map to build the sorted result matrix.
**Time:** O(m log m + m*n). Inserting `m` elements into a `TreeMap` takes O(m log m) time. Iterating through the map and building the result matrix takes O(m*n) time to copy all the data. · **Space:** O(m*n). The `TreeMap` stores all `m` rows, where each row has `n` integers. The result matrix also requires O(m*n) space.
**Pros:** A clean and structured way to sort using a standard data structure.; Guarantees O(log m) time per insertion, leading to an overall efficient sorting time.
**Cons:** Requires significant extra space, O(m*n), to store both the `TreeMap` and the result matrix.; The time complexity includes an O(m*n) term for copying rows, making it slightly less efficient than the optimal in-place sort.
### Explanation
A `TreeMap` in Java stores key-value pairs and guarantees that the keys are kept in ascending order. We can exploit this by mapping each student's k-th score to their entire row of scores. After populating the map, the students are effectively sorted by their k-th score. We then create a new matrix and fill it by iterating through the map's entries. To achieve the required descending order, we can either iterate through the map's values and fill the result array from back to front, or use the `descendingMap()` method to iterate in the desired order.

```java
import java.util.TreeMap;
import java.util.Map;

class Solution {
    public int[][] sortTheStudents(int[][] score, int k) {
        int m = score.length;
        int n = score[0].length;
        
        // TreeMap sorts keys in ascending order by default.
        Map<Integer, int[]> map = new TreeMap<>();
        for (int i = 0; i < m; i++) {
            map.put(score[i][k], score[i]);
        }
        
        int[][] result = new int[m][n];
        int index = m - 1;
        // Iterate through the values to get them in ascending order of keys
        // and place them from the end of the result array for descending order.
        for (int[] row : map.values()) {
            result[index--] = row;
        }
        
        return result;
    }
}
```
### Algorithm
*   Create a `TreeMap<Integer, int[]>`, which stores entries sorted by key.
*   Iterate through the `score` matrix. For each row `i`, insert an entry `(score[i][k], score[i])` into the `TreeMap`.
*   The `TreeMap` will automatically maintain the entries sorted in ascending order of the scores (the keys).
*   Create a new result matrix `result` of size `m x n`.
*   To get descending order, iterate through the `TreeMap`'s values and place them in the `result` matrix from the end to the beginning. Alternatively, use `descendingKeySet()` to iterate in reverse.
*   Return the `result` matrix.

## Optimal: Built-in Sort with Custom Comparator
The most efficient and idiomatic way to solve this problem is to use the built-in sorting function provided by the programming language. These functions are highly optimized (typically implementing an O(m log m) algorithm like TimSort or IntroSort) and allow for custom comparison logic via a comparator or a key function. This allows us to sort the matrix in-place with optimal time and space complexity.
**Time:** O(m log m). We are sorting `m` rows. The underlying sort algorithm runs in O(m log m) time. Each comparison and swap operation on the row references takes constant O(1) time. · **Space:** O(log m) or O(m). The space complexity depends on the implementation of the sorting algorithm. For TimSort (used in Java for object arrays), it's O(log m) on average and O(m) in the worst case for the internal stack.
**Pros:** Most efficient in terms of time complexity.; Space-efficient as sorting can be done in-place.; Concise, readable, and leverages the highly optimized and tested standard library.
**Cons:** This approach has no significant cons for this problem; it is the standard and most effective solution.
### Explanation
We can directly sort the `score` matrix, which is an array of arrays (`int[][]`). We treat each inner array (`int[]`) as an element to be sorted. The `Arrays.sort` method in Java can take a `Comparator` to define a custom sorting rule. We provide a lambda expression `(a, b) -> Integer.compare(b[k], a[k])` as the comparator. This tells the sort function to compare any two rows `a` and `b` based on their values at index `k`. By comparing `b[k]` to `a[k]`, we achieve a descending order sort. The sorting is done in-place, modifying the original `score` matrix.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int[][] sortTheStudents(int[][] score, int k) {
        // Sort the score matrix directly using a custom comparator.
        // The comparator compares two rows based on their k-th element.
        // Integer.compare(b[k], a[k]) sorts in descending order.
        Arrays.sort(score, (a, b) -> Integer.compare(b[k], a[k]));
        return score;
    }
}
```
### Algorithm
*   Call the standard library's sort function (e.g., `Arrays.sort` in Java) on the `score` matrix.
*   Provide a custom comparator (e.g., a lambda expression) that defines the sorting order.
*   The comparator takes two rows, `a` and `b`, as input.
*   It should compare the elements at index `k`: `a[k]` and `b[k]`.
*   To sort in descending order, the comparator should return a positive value if `a[k]` should come after `b[k]`. This is achieved by comparing `b[k]` with `a[k]` (e.g., `b[k] - a[k]`).

# Solutions
### Java

```java
class Solution {
public
  int[][] sortTheStudents(int[][] score, int k) {
    Arrays.sort(score, (a, b)->b[k] - a[k]);
    return score;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> sortTheStudents(vector<vector<int>> &score, int k) {
    sort(score.begin(), score.end(),
         [&](const auto &a, const auto &b) { return a[k] > b[k]; });
    return score;
  }
};

```

### Python

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

```