Problem Description

You are given a 2D integer array of student data students, where students[i] = [student_id, bench_id] represents that student student_id is sitting on the bench bench_id.

Return the maximum number of unique students sitting on any single bench. If no students are present, return 0.

Note: A student can appear multiple times on the same bench in the input, but they should be counted only once per bench.

Intuition

To solve this problem, the key is to keep track of which students are sitting on which benches and ensure that each student is counted only once per bench.

1. Data Structure Choice: Use a hash table to map each bench_id to a set of student_ids. This way, we can easily ensure that each student is counted uniquely for each bench, as sets automatically handle duplicate entries.

2. Processing the Data: Iterate over the list of student-bench pairs. For each pair, add the student ID to the set associated with the corresponding bench ID in the hash table. This allows us to collect all unique students sitting on each bench.

3. Calculating the Result: After populating the hash table, the task is to find the bench with the maximum number of unique students. This can be achieved by checking the size of each set in the hash table and returning the largest size found.

Using these steps ensures that the solution is both efficient and accurate, leveraging data structures that naturally align with the problem's requirements.

Solution Approach

To implement the solution, we'll follow a structured approach using a hash table, as described in the reference solution.

1. Check for Empty List: Start by checking if the students list is empty. If it is, return 0 immediately, as there are no students present.

2. Initialize the Hash Table: Use a defaultdict from the collections module, where each key is a bench_id and its value is a set. The set will store the unique student_ids for that bench.

3. Populate the Hash Table: Iterate over each student entry in the students list. For each [student_id, bench_id], add the student_id to the set associated with the corresponding bench_id in the hash table. By using a set, we automatically handle duplicate entries, ensuring each student is counted only once per bench.

4. Determine the Maximum: Once the hash table is populated, calculate the maximum number of unique students sitting on any single bench. This can be done by finding the length of the largest set in the hash table, which can be efficiently achieved by using the max function with map(len, d.values()).

The code implementing this logic is as follows:

class Solution:
    def maxStudentsOnBench(self, students: List[List[int]]) -> int:
        if not students:
            return 0
        d = defaultdict(set)
        for student_id, bench_id in students:
            d[bench_id].add(student_id)
        return max(map(len, d.values()))

This solution efficiently solves the problem by leveraging the properties of hash tables and sets. It ensures that operations like counting unique students per bench and finding maximum values are both simple and efficient.

Example Walkthrough

Let's walk through an example to illustrate the solution approach.

Example Input

Suppose we have the following input list of students and benches:

students = [
    [1, 101],
    [2, 101],
    [1, 102],
    [3, 101],
    [2, 102],
    [2, 101]
]

This example shows that:

• Student 1 is sitting on benches 101 and 102.
• Student 2 is sitting on benches 101 and 102.
• Student 3 is sitting on bench 101.
• Student 2 is listed twice on bench 101, but should only be counted once.

Step-by-Step Solution

1. Check for Empty List: Here, the students list is not empty, so we proceed with the initialization.

2. Initialize the Hash Table: Create a defaultdict where each key corresponds to a bench_id, and the value is a set to store unique student_ids.

3. Populate the Hash Table: Iterate over each pair in the students list.

   • For the pair [1, 101], add student 1 to the set for bench 101: {101: {1}}.
   • For the pair [2, 101], add student 2 to the set for bench 101: {101: {1, 2}}.
   • For the pair [1, 102], add student 1 to the set for bench 102: {101: {1, 2}, 102: {1}}.
   • For the pair [3, 101], add student 3 to the set for bench 101: {101: {1, 2, 3}, 102: {1}}.
   • For the pair [2, 102], add student 2 to the set for bench 102: {101: {1, 2, 3}, 102: {1, 2}}.
   • The duplicate entry [2, 101] does not change the set, as student 2 is already included: {101: {1, 2, 3}, 102: {1, 2}}.

4. Determine the Maximum: Calculate the maximum number of unique students for any bench by checking the sizes of these sets. In this example, for bench 101 we have 3 unique students, and for bench 102 we have 2 unique students.

   Thus, the maximum number of unique students sitting on any single bench is:

   max(3, 2) = 3

Conclusion

The function would return 3, meaning the maximum number of unique students on one bench is 3.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n), where n is the number of elements in the students list. This is because the code iterates over each student exactly once to populate the dictionary d.

The space complexity of the code is also O(n), as the dictionary d stores each student in a set, and in the worst case, each student is associated with a unique bench, resulting in O(n) space used.

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