Problem Description

You have a classroom with m students and n exams. Each student has taken all n exams and received scores for each one.

You're given a 2D matrix called score where:

• Each row represents one student
• Each column represents one exam
• score[i][j] is the score that student i got on exam j
• All scores in the matrix are distinct (no two scores are the same)

Your task is to sort the students based on their performance in a specific exam. Given an integer k, you need to:

1. Look at the scores from the k-th exam (column k)
2. Sort all students (rows) based on these scores
3. Arrange students from highest score to lowest score in that exam

The solution uses Python's built-in sorted() function with a custom key. The key lambda x: -x[k] extracts the score from column k for each row x, and the negative sign ensures descending order sorting. This efficiently reorders all rows of the matrix based on the values in the specified column.

For example, if k = 1 and you have scores for 3 students and 2 exams, the students would be reordered so that whoever scored highest on exam 1 appears first, then the second-highest scorer, and so on.

Intuition

The problem essentially asks us to rearrange rows of a matrix based on values in a specific column. This is a classic sorting problem with a twist - instead of sorting a single array, we're sorting entire rows while using one particular column as the sorting criterion.

When we need to sort students by their scores in the k-th exam, we're really just sorting the rows of the matrix based on the values at index k in each row. Think of it like sorting a list of people by their age - you look at one specific attribute (age) to determine the order, but you move the entire person record when reordering.

The key insight is that Python's sorted() function can handle this elegantly. We can pass the entire matrix and specify a custom sorting key that extracts just the value we care about from each row. Since we want descending order (highest scores first), we can either:

1. Use sorted() with reverse=True
2. Negate the value in our key function (turning large positive values into large negative values)

The second approach with -x[k] is more concise. When Python sorts by negative values, what was originally the largest positive value becomes the smallest negative value and appears first in the sorted result. For instance, if exam scores are [85, 92, 78], negating gives [-85, -92, -78], and sorting these in ascending order gives [-92, -85, -78], which corresponds to the original values [92, 85, 78] - exactly the descending order we want.

This approach works because we're guaranteed all scores are distinct, so there are no ties to worry about. Each row will have a unique position in the final sorted order based on its score in column k.

Learn more about Sorting patterns.

Solution Approach

The solution uses Python's built-in sorted() function to rearrange the rows of the matrix based on scores in the k-th column.

Implementation Details:

1. Input Parameters:

   • score: A 2D list representing the matrix of student scores
   • k: The index of the exam column to sort by

2. Sorting Mechanism:

   • We call sorted(score, key=lambda x: -x[k])
   • The sorted() function creates a new sorted list from the input
   • Each element being sorted is a row (a list of scores for one student)

3. Key Function:

   • lambda x: -x[k] is an anonymous function that:
     • Takes a row x as input
     • Accesses the score at position k using x[k]
     • Returns the negative of that score -x[k]

4. Why Negative Values:

   • By default, sorted() arranges elements in ascending order
   • We want descending order (highest scores first)
   • Negating the values reverses the order: the highest positive score becomes the lowest negative value
   • Example: If column k has values [75, 90, 82], the key function returns [-75, -90, -82]
   • Sorting these gives [-90, -82, -75], which corresponds to rows with original scores [90, 82, 75]

5. Time and Space Complexity:

   • Time Complexity: O(m log m) where m is the number of students (rows), as we're sorting m elements
   • Space Complexity: O(m) for the sorted list that's returned

The beauty of this approach is its simplicity - Python's sorting infrastructure handles all the heavy lifting of maintaining row integrity while reordering based on a single column's values.

Example Walkthrough

Let's work through a concrete example to understand how the solution works.

Given:

• A classroom with 4 students and 3 exams
• Score matrix:

       Exam0  Exam1  Exam2
Student 0: [10,    6,    9]
Student 1: [7,     5,    3]
Student 2: [8,     11,   2]
Student 3: [9,     7,    1]

• We want to sort by k = 1 (Exam 1)

Step 1: Identify the sorting column Look at column k = 1 (Exam 1 scores):

• Student 0: score = 6
• Student 1: score = 5
• Student 2: score = 11
• Student 3: score = 7

Step 2: Apply the key function The lambda function lambda x: -x[k] transforms each row:

• Student 0: -x[1] = -6
• Student 1: -x[1] = -5
• Student 2: -x[1] = -11
• Student 3: -x[1] = -7

Step 3: Sort based on transformed values Python sorts these negative values in ascending order: [-11, -7, -6, -5]

This ordering corresponds to the original rows with scores: [11, 7, 6, 5]

Step 4: Final result The rows are reordered according to this sorting:

       Exam0  Exam1  Exam2
Student 2: [8,     11,   2]   (highest Exam 1 score: 11)
Student 3: [9,     7,    1]   (second highest: 7)
Student 0: [10,    6,    9]   (third highest: 6)
Student 1: [7,     5,    3]   (lowest: 5)

The students are now arranged from highest to lowest score in Exam 1, with each student's complete row of scores moved as a unit.

Solution Implementation

Time and Space Complexity

The time complexity is O(m × log m), where m is the number of rows in the score matrix. This is because the sorted() function uses Timsort algorithm, which has a time complexity of O(n log n) for sorting n elements. In this case, we're sorting m rows based on the value at index k in each row.

The space complexity is O(log m). While sorted() creates a new list which would typically require O(m) space, the space complexity analysis here refers to the auxiliary space used by the sorting algorithm itself. Timsort requires O(log n) space for its recursive calls and temporary storage during the merge operations. Since we're sorting m rows, this translates to O(log m) auxiliary space complexity.

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

Common Pitfalls

1. Modifying the Original Matrix Instead of Returning a New One

A common mistake is trying to sort the matrix in-place using list.sort() instead of sorted(), which can lead to unexpected behavior if the caller expects the original matrix to remain unchanged.

Incorrect approach:

def sortTheStudents(self, score: List[List[int]], k: int) -> List[List[int]]:
    score.sort(key=lambda x: -x[k])  # Modifies the original matrix!
    return score

Correct approach:

def sortTheStudents(self, score: List[List[int]], k: int) -> List[List[int]]:
    return sorted(score, key=lambda x: -x[k])  # Returns a new sorted matrix

2. Index Out of Bounds Error

Failing to validate that k is within valid column bounds can cause runtime errors. If k >= n (where n is the number of exams), accessing x[k] will raise an IndexError.

Solution with validation:

def sortTheStudents(self, score: List[List[int]], k: int) -> List[List[int]]:
    # Validate k is within bounds
    if not score or not score[0] or k < 0 or k >= len(score[0]):
        return score
  
    return sorted(score, key=lambda x: -x[k])

3. Confusion Between Ascending and Descending Order

Forgetting to negate the value in the key function results in ascending order (lowest scores first) instead of the required descending order.

Wrong (ascending order):

sorted(score, key=lambda x: x[k])  # Lowest scores first

Correct (descending order):

sorted(score, key=lambda x: -x[k])  # Highest scores first

4. Using reverse=True with Positive Values

While using reverse=True parameter achieves the same result, mixing approaches can lead to confusion when maintaining code.

Alternative (also correct but different style):

sorted(score, key=lambda x: x[k], reverse=True)

Choose one approach consistently throughout your codebase for better readability.