Sort the Students by Their Kth Score

Medium

Asked by:

15 views

Topics:

Arrays

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 i^th student got in the j^th 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 k^th (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.length
n == score[i].length
1 <= m, n <= 250
1 <= score[i][j] <= 10⁵
score consists of distinct integers.
0 <= k < n

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the dimensions of the `score` matrix (number of students and number of subjects)?
Are the scores in the `score` matrix guaranteed to be non-negative integers?
If multiple students have the same score in the k-th subject, what should be the order of those students in the sorted matrix?
Is the value of `k` guaranteed to be a valid column index within the `score` matrix (i.e., 0 <= k < number of subjects)?
Can the input `score` matrix be empty, or have zero rows or zero columns? If so, what should I return?

Brute Force Solution

Approach

The brute force approach is to try every possible order of students, compare them based on their score in the specified subject, and find the correct order. This method is like shuffling cards and checking if they are in the correct sequence, repeating until the right sequence is found.

Here's how the algorithm would work step-by-step:

Start by listing all the possible ways to arrange the students.
For each possible arrangement, look at the score of each student in the specified subject.
Compare the scores in the specified subject to determine if the current arrangement is sorted correctly.
If the arrangement is sorted correctly based on the specified subject scores, then this is our answer.
If we have checked all possible arrangements and none are correct, something went wrong. Otherwise, we have our sorted list.

Code Implementation

def sort_the_students_brute_force(student_scores, sort_by_column):
    import itertools
    number_of_students = len(student_scores)
    student_indices = list(range(number_of_students))

    # Generate all possible permutations of student indices.
    all_possible_arrangements = list(itertools.permutations(student_indices))

    for student_arrangement in all_possible_arrangements:
        is_sorted = True
        # Check if the current arrangement is sorted correctly.
        for i in range(number_of_students - 1):
            if student_scores[student_arrangement[i]][sort_by_column] <\
               student_scores[student_arrangement[i+1]][sort_by_column]:
                is_sorted = False
                break

        # If an arrangement is sorted correctly return it.
        if is_sorted:
            sorted_student_scores = []
            for student_index in student_arrangement:
                sorted_student_scores.append(student_scores[student_index])
            return sorted_student_scores

    return []

Big(O) Analysis

Time Complexity

O(n! * n) – The brute force approach iterates through all possible permutations (arrangements) of the n students. There are n! (n factorial) such permutations. For each permutation, the algorithm compares the kth score of each student to determine if the arrangement is sorted, which requires iterating through the list of students, taking O(n) time. Therefore, the overall time complexity is O(n! * n).

Space Complexity

O(N!) – The brute force approach generates all possible permutations of the students. Generating all permutations of N students requires storing a list of these permutations. The number of permutations grows factorially with the number of students, specifically, N! permutations. Therefore, the auxiliary space required to store all permutations is proportional to N!.

Optimal Solution

Approach

The goal is to rearrange student records based on their score in a specific subject. We can achieve this efficiently by using a sorting method that focuses on comparing students' scores in that subject only, then rearranging them accordingly.

Here's how the algorithm would work step-by-step:

Choose the subject (column) that you want to use to sort the students.
Compare the scores of each student in that specific subject to every other student.
Arrange the students based on these comparisons, so the student with the highest score in that subject comes first, followed by the student with the next highest, and so on until the student with the lowest score is last.
Return the entire list of students rearranged based on their scores in the selected subject.

Code Implementation

def sort_the_students(student_scores, k_index):
    # Attach the kth score as a sorting key to each student.
    student_with_kth_score = [(student, student[k_index]) for student in student_scores]

    # Sort students by their kth score in descending order.

    sorted_students = sorted(student_with_kth_score, key=lambda item: item[1], reverse=True)

    # Return only the sorted student records.
    return [student for student, score in sorted_students]

Big(O) Analysis

Time Complexity

O(n²) – The given approach iterates through the list of students and compares the score of each student in the chosen subject with every other student to determine the sorted order. This involves comparing each of the 'n' students with the remaining 'n-1' students, leading to nested loops. Therefore, the number of comparisons grows proportionally to n * (n-1), which simplifies to approximately n². This means the time complexity is O(n²).

Space Complexity

O(1) – The plain English explanation outlines a sorting procedure involving comparisons and rearranging student records in place. No auxiliary data structures like temporary lists or hash maps are explicitly mentioned. The algorithm works by directly comparing scores within the input and rearranging the existing data structure; hence, it doesn't create new structures that scale with the number of students. Therefore, the space complexity is constant, meaning it does not depend on the number of students, N.

Edge Cases

Case	How to Handle
score is null or empty	Return an empty array or null to indicate invalid input.
k is out of bounds (k < 0 or k >= number of subjects)	Throw an IllegalArgumentException or return null/empty array to signal invalid k.
score has only one student	Return the input score array directly since it is already sorted.
score has rows with different lengths	Throw an IllegalArgumentException because inconsistent input is invalid.
All students have the same score at index k	The sorting algorithm should maintain the original order of these students (stable sort).
Large input size that could lead to performance issues with naive sorting algorithms	Use an efficient sorting algorithm (e.g., merge sort, quicksort) with O(n log n) time complexity.
score contains negative numbers	The sorting algorithm should correctly handle negative numbers by sorting based on numerical value.
Integer overflow when comparing student scores	Use long or double for intermediate calculations and comparisons to prevent overflow.

score is null or empty

How to Handle:

Return an empty array or null to indicate invalid input.

k is out of bounds (k < 0 or k >= number of subjects)

How to Handle:

Throw an IllegalArgumentException or return null/empty array to signal invalid k.

score has only one student

How to Handle:

Return the input score array directly since it is already sorted.

score has rows with different lengths

How to Handle:

Throw an IllegalArgumentException because inconsistent input is invalid.

All students have the same score at index k

How to Handle:

The sorting algorithm should maintain the original order of these students (stable sort).

Large input size that could lead to performance issues with naive sorting algorithms

How to Handle:

Use an efficient sorting algorithm (e.g., merge sort, quicksort) with O(n log n) time complexity.

score contains negative numbers

How to Handle:

The sorting algorithm should correctly handle negative numbers by sorting based on numerical value.

Integer overflow when comparing student scores

How to Handle:

Use long or double for intermediate calculations and comparisons to prevent overflow.