Sort the Students by Their Kth Score solution and explanation
IBM
9 more videos on this problem
2545. Sort the Students by Their Kth Score | Weekly Contest 329 | LeetCode 2545Bro Coders · 5:44 · 2K views
Leetcode 2545: Sort the Students by Their Kth Score (Weekly Contest 329)Algorithms Casts · 4:36 · 865 views
Sort the Students by Their Kth Score | leetcode Weekly 329 | Leetcode MediumBinaryMagic · 5:38 · 610 views
Leetcode 2545 Sort the Students by Their Kth Score (Java) - Leetcode Contest 330TheAnalyticGuy · 2:27 · 494 views
2545. Sort the Students by Their Kth Score ll Java Solution || Weekly Contest 329ExpertFunda · 1:37 · 439 views
sort the students by their kth score || weekly contest 329 || #leetcode || C++ SolutionCode With U-DAY · 5:41 · 392 views
Sort the Students by Their Kth Score || LeetCode Weekly Contest 329 Solution with ExplanationLearn to Code · 2:53 · 294 views
2545. Sort the Students by Their Kth Score (Leetcode Medium)Programming Live with Larry · 2:43 · 227 views
Sort the Students by Their Kth Score | Leetcode 2545 | Leetcode Weekly Contest 329Tech Courses · 5:08 · 227 views
2545. Sort the Students by Their Kth Score || Leetcode Weekly Contest 329 || Question NO.2CodeVed | Sanjib Asiwal · 7:01 · 162 views
The 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:
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:
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.lengthn == score[i].length1 <= m, n <= 2501 <= score[i][j] <= 105scoreconsists of distinct integers.0 <= k < n
Approach overview
Problem Overview: You are given a matrix where each row represents a student and each column represents a score in a particular exam. The task is to sort all students in descending order based on their score in the kth column while keeping each student's full score row intact.
Approach 1: Direct Sorting Using Custom Comparator (O(n log n) time, O(1) extra space)
The most straightforward solution sorts the matrix rows using the value at column k as the sorting key. Use the built‑in sorting function and provide a custom comparator (or key function) that compares row[k]. Since sorting algorithms typically run in O(n log n) for n students, the overall runtime follows the same complexity. No additional data structures are required beyond the sorting stack, so auxiliary space is O(1) or O(log n) depending on the language implementation. This approach is concise and leverages optimized standard library sorting.
Approach 2: Using a Priority Queue (Heap Approach) (O(n log n) time, O(n) space)
Another option pushes each student row into a max‑heap keyed by the kth score. Each heap node stores the full row so the matrix structure remains intact. Building the heap takes O(n) time, and extracting all students in sorted order requires n pop operations, each costing O(log n). The resulting rows are collected in descending order of the kth score. This method uses O(n) additional space for the heap but provides flexibility when you need partial ordering or top‑k extraction.
The problem mainly tests familiarity with array manipulation and built‑in sorting utilities while handling a 2D matrix structure. The key insight is that the sorting key is a single column value, but the entire row must move together during reordering.
Recommended for interviews: Direct sorting with a custom comparator. It is the most idiomatic solution and clearly shows you understand how to sort structured data by a specific key. Mentioning the heap approach demonstrates awareness of alternative ordering techniques, but interviewers typically expect the comparator‑based sort.
Approach 1: Direct Sorting Using Custom Comparator
In this approach, we directly use a sorting function and provide a custom comparator. This comparator sorts the 2D array (list of lists) based on the kth element of each row. Most programming languages have a built-in sort function that allows specifying custom comparison logic, either through a lambda function or similar constructs.
This approach leverages the power of built-in sorting functions that are generally well-optimized.
def sort_scores(scores, k):
scores.sort(key=lambda x: x[k], reverse=True)
# Example usage
scores = [[10, 6, 9, 1], [7, 5, 11, 2], [4, 8, 3, 15]]
k = 2
sort_scores(scores, k)
for row in scores:
print(row)import java.util.Arrays;
public class Main {
public static void sortScores(int[][] scores, int k) {
Arrays.sort(scores, (a, b) -> Integer.compare(b[k], a[k]));
}
public static void main(String[] args) {
int[][] scores = {{10, 6, 9, 1}, {7, 5, 11, 2}, {4, 8, 3, 15}};
int k = 2;
sortScores(scores, k);
for (int[] row : scores) {
for (int score : row) {
System.out.print(score + " ");
}
System.out.println();
}
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void sortScores(vector<vector<int>>& scores, int k) {
sort(scores.begin(), scores.end(), [k](const vector<int>& a, const vector<int>& b) {
return a[k] > b[k];
});
}
int main() {
vector<vector<int>> scores = {{10, 6, 9, 1}, {7, 5, 11, 2}, {4, 8, 3, 15}};
int k = 2;
sortScores(scores, k);
for (const auto& row : scores) {
for (int score : row) {
cout << score << " ";
}
cout << endl;
}
return 0;
}function sortScores(scores, k) {
scores.sort((a, b) => b[k] - a[k]);
}
const scores = [
[10, 6, 9, 1],
[7, 5, 11, 2],
[4, 8, 3, 15]
];
const k = 2;
sortScores(scores, k);
console.log(scores);#include <stdio.h>
#include <stdlib.h>
int cmp(const void* a, const void* b, void* arg) {
int k = *(int*)arg;
int* rowA = *(int**)a;
int* rowB = *(int**)b;
return (rowB[k] - rowA[k]); // descending order
}
void sortScores(int** score, int m, int n, int k) {
qsort_r(score, m, sizeof(int*), cmp, &k);
}
int main() {
int m = 3, n = 4, k = 2;
int data[3][4] = {{10, 6, 9, 1}, {7, 5, 11, 2}, {4, 8, 3, 15}};
int* score[3] = {data[0], data[1], data[2]};
sortScores(score, m, n, k);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", score[i][j]);
}
printf("\n");
}
return 0;
}using System;
using System.Linq;
public class Program {
public static void SortScores(int[][] scores, int k) {
Array.Sort(scores, (a, b) => b[k].CompareTo(a[k]));
}
public static void Main() {
int[][] scores = new int[][] {
new int[] {10, 6, 9, 1},
new int[] {7, 5, 11, 2},
new int[] {4, 8, 3, 15}
};
int k = 2;
SortScores(scores, k);
foreach (var row in scores) {
Console.WriteLine(string.Join(" ", row));
}
}
}This Python solution makes use of the built-in sort method on lists with the key parameter. It sorts the list of lists based on the kth element in descending order by setting reverse=True.
Time Complexity: O(m log m), where m is the number of students. Space Complexity: O(1) since the sort is in-place.
Approach 2: Using a Priority Queue (Heap Approach)
This approach uses a priority queue (or heap) to keep track of the highest scoring students based on the kth exam score. By building a max-heap based on the kth score, we efficiently retrieve students in the desired order. This approach is particularly valuable when we only need part of the sorted data.
import heapq
def sort_scores(scores, k):
# Use a max-heap
scores = [(-score[k], score) for score in scores]
heapq.heapify(scores)
sorted_scores = []
while scores:
sorted_scores.append(heapq.heappop(scores)[1])
return sorted_scores
scores = [[10, 6, 9, 1], [7, 5, 11, 2], [4, 8, 3, 15]]
k = 2
sorted_scores = sort_scores(scores, k)
for row in sorted_scores:
print(row)import java.util.PriorityQueue;
import java.util.Arrays;
public class Main {
public static int[][] sortScores(int[][] scores, int k) {
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(b[k], a[k]));
for (int[] score : scores) {
pq.add(score);
}
int[][] sortedScores = new int[scores.length][];
int index = 0;
while (!pq.isEmpty()) {
sortedScores[index++] = pq.poll();
}
return sortedScores;
}
public static void main(String[] args) {
int[][] scores = {{10, 6, 9, 1}, {7, 5, 11, 2}, {4, 8, 3, 15}};
int k = 2;
int[][] sortedScores = sortScores(scores, k);
for (int[] row : sortedScores) {
System.out.println(Arrays.toString(row));
}
}
}#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, vector<int>> pi;
vector<vector<int>> sortScores(vector<vector<int>>& scores, int k) {
priority_queue<pi> pq;
for (auto& score : scores) {
pq.push({score[k], score});
}
vector<vector<int>> result;
while (!pq.empty()) {
result.push_back(pq.top().second);
pq.pop();
}
return result;
}
int main() {
vector<vector<int>> scores = {{10, 6, 9, 1}, {7, 5, 11, 2}, {4, 8, 3, 15}};
int k = 2;
vector<vector<int>> sortedScores = sortScores(scores, k);
for (const auto& row : sortedScores) {
for (int score : row) {
cout << score << " ";
}
cout << endl;
}
return 0;
}This Python code leverages a max-heap by negating the kth values to maintain descending order. The heapq library is used to perform heap operations, effectively sorting scores by the kth exam value.
Time Complexity: O(m log m) for heap operations. Space Complexity: O(m) for the heap's storage requirements.
Approach 3: Sorting
We directly sort score in descending order based on the scores in the k-th column, and then return the result.
The time complexity is O(m times log m), and the space complexity is O(log m). Here, m is the number of rows in score.
function sortTheStudents(score: number[][], k: number): number[][] {
return score.sort((a, b) => b[k] - a[k]);
}func sortTheStudents(score [][]int, k int) [][]int {
sort.Slice(score, func(i, j int) bool { return score[i][k] > score[j][k] })
return score
}impl Solution {
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]));
score
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Direct Sorting Using Custom Comparator | Time Complexity: O(m log m), where m is the number of students. Space Complexity: O(1) since the sort is in-place. |
| Using a Priority Queue (Heap Approach) | Time Complexity: O(m log m) for heap operations. Space Complexity: O(m) for the heap's storage requirements. |
| Sorting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Sorting Using Custom Comparator | O(n log n) | O(1) or O(log n) | Best general solution when you need the entire matrix sorted by the kth column |
| Priority Queue (Heap) | O(n log n) | O(n) | Useful when you already use a heap or when extracting top‑k rows instead of fully sorting |
Frequently asked questions
Is Sort the Students by Their Kth Score easy or hard?
LeetCode classifies this problem as Medium, but the logic is straightforward if you know how to sort arrays with a custom key. The main challenge is recognizing that you must sort rows based on a specific column while preserving the entire row structure.
Sort the Students by Their Kth Score Python/Java solution
In Python, use sorted(score, key=lambda row: row[k], reverse=True). In Java, use Arrays.sort(score, (a, b) -> Integer.compare(b[k], a[k])). Both implementations sort rows by the kth score in descending order with O(n log n) time complexity.
How to solve Sort the Students by Their Kth Score in O(n)?
Achieving strict O(n) time is generally not possible because the problem requires ordering all rows, which requires comparison-based sorting. Standard algorithms such as quicksort or mergesort take O(n log n). Only specialized scenarios with limited value ranges could approach linear-time techniques like counting sort, but that constraint is not guaranteed here.
What is the best approach for Sort the Students by Their Kth Score?
The best approach is sorting the matrix rows using a custom comparator based on the kth column value. Built‑in sorting functions allow you to pass a key such as row[k], which keeps each student's entire row intact while ordering them by that score. This solution runs in O(n log n) time and requires minimal additional space.
Is Sort the Students by Their Kth Score asked at Google/Amazon/Meta?
Sorting-based matrix problems appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, interviewers often ask candidates to sort objects or rows of data using a specific key, which tests familiarity with comparators and standard library sorting.
What data structure is used in Sort the Students by Their Kth Score?
The primary structure is a 2D array (matrix) representing students and their exam scores. The optimal solution relies on a sorting algorithm with a custom comparator. An alternative approach uses a priority queue (max‑heap) keyed by the kth score to produce the sorted order.
What is the time complexity of Sort the Students by Their Kth Score?
The typical solution sorts the student rows by the kth score, which takes O(n log n) time for n students. Accessing the kth element during comparison is O(1), so it does not affect the complexity. Space complexity is O(1) or O(log n) depending on the language's sorting implementation.