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.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4
5

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] <= 10^5
  • score consists of distinct integers.
  • 0 <= k < n

Solution

Method 1 - Custom Comparator Sorting

Intuition

We need to sort the matrix rows based on the kth column values in descending order (highest to lowest). Each row represents a student, and we want to reorder students by their performance in the kth exam.

Approach

  1. Use a custom comparator that compares rows based on the kth column value
  2. Sort in descending order since we want highest scores first
  3. The sorting will rearrange entire rows, preserving each student’s complete score profile

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> sortTheStudents(vector<vector<int>>& score, int k) {
    sort(score.begin(), score.end(), [k](const vector<int>& a, const vector<int>& b) {
        return a[k] > b[k]; // Sort by kth column in descending order
    });
    return score;
}
1
2
3
4
5
6
7
8

import "sort"

func sortTheStudents(score [][]int, k int) [][]int {
    sort.Slice(score, func(i, j int) bool {
        return score[i][k] > score[j][k] // Sort by kth column in descending order
    })
    return score
}
1
2
3
4
5
6
7
8

import java.util.Arrays;

class Solution {
    public int[][] sortTheStudents(int[][] score, int k) {
        Arrays.sort(score, (a, b) -> Integer.compare(b[k], a[k])); // Descending order
        return score;
    }
}
1
2
3
4
5
6

class Solution {
    fun sortTheStudents(score: Array<IntArray>, k: Int): Array<IntArray> {
        score.sortByDescending { it[k] }
        return score
    }
}
1
2
3
4

def sortTheStudents(score: list[list[int]], k: int) -> list[list[int]]:
    # Sort by kth column in descending order
    score.sort(key=lambda student: student[k], reverse=True)
    return score
1
2
3
4
5

pub fn sort_the_students(mut score: Vec<Vec<i32>>, k: i32) -> Vec<Vec<i32>> {
    let k = k as usize;
    score.sort_by(|a, b| b[k].cmp(&a[k])); // Sort by kth column in descending order
    score
}
1
2
3
4

function sortTheStudents(score: number[][], k: number): number[][] {
    score.sort((a, b) => b[k] - a[k]); // Sort by kth column in descending order
    return score;
}

Complexity

  • ⏰ Time complexity: O(m log m) where m is the number of students (rows)
  • 🧺 Space complexity: O(1) if sorting in-place, O(m) for the sorting algorithm’s internal space