Skip to content

Latest commit

 

History

History
81 lines (53 loc) · 3.48 KB

032.md

File metadata and controls

81 lines (53 loc) · 3.48 KB

2545. Sort the Students by Their Kth Score

Difficulty: 🟡 Medium

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:

032_01.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:

032_02.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

Solutions

O(m*log(m)) solution in Python3

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

The given solution sorts the matrix score based on the scores of students in the kth exam using the sorted() function and a lambda function as the key.

The algorithm works as follows:

  1. Use the sorted() function to sort the matrix score based on the scores in the kth exam.
    • Provide the score matrix as the iterable to be sorted.
    • Use a lambda function as the key to specify the sorting criterion. The lambda function takes each row x from the matrix and returns the score of the kth exam for that row (x[k]).
    • Set the reverse parameter to True to sort the rows in descending order based on the kth exam scores.
  2. Return the sorted matrix.

The algorithm sorts the matrix score based on the kth exam scores of the students, in descending order.

Analysis of Time and Space Complexity

The time complexity of this algorithm is O(m log m), where m is the number of rows (students) in the score matrix. The sorted() function performs a stable sorting operation with a time complexity of O(m log m).

The space complexity of the algorithm is O(m), as it creates a new list to store the sorted matrix.

Summary

The given solution sorts the matrix score based on the scores of students in the kth exam in descending order. It has a time complexity of O(m log m) and a space complexity of O(m), making it an efficient solution for the problem at hand.

NB: If you want to get community points please suggest solutions in other languages as merge requests.