Problem Description

You are given a 2D integer array called students, where each element students[i] = [student_id, bench_id] indicates that a student with ID student_id is sitting on bench number bench_id.

Your task is to find the maximum number of unique students sitting on any single bench. If there are no students in the input array, return 0.

An important detail to note: The same student can appear multiple times on the same bench in the input data (multiple entries with the same student_id and bench_id), but when counting students on a bench, each unique student should only be counted once.

For example:

• If the input contains [[1, 2], [1, 2], [3, 2]], bench 2 has only 2 unique students (student 1 and student 3), not 3.
• The goal is to find which bench has the most unique students and return that count.

The solution uses a hash table with sets to track unique students per bench. For each bench, it maintains a set of student IDs (automatically handling duplicates), then returns the size of the largest set.

Intuition

The key insight is recognizing that we need to count unique students per bench, not total occurrences. When we see multiple entries for the same student on the same bench, we should count that student only once for that bench.

This naturally leads us to think about using a data structure that automatically handles uniqueness - a set. Sets inherently prevent duplicates, so if we add the same student ID multiple times, it will only be stored once.

Since we need to track students for multiple benches, we need a way to organize our sets by bench ID. This points us toward using a hash table (dictionary) where:

• Each key represents a bench ID
• Each value is a set containing all unique student IDs on that bench

As we iterate through the input array, we can simply add each student to the corresponding bench's set. The set automatically handles the deduplication for us - if student 1 appears on bench 2 multiple times, adding them to d[2] repeatedly won't increase the set size beyond 1 for that student.

Once we've processed all entries, finding the answer becomes straightforward: we just need to find which bench's set has the most elements. This is simply the maximum size among all the sets in our hash table.

The elegance of this approach is that we let the data structures do the heavy lifting - the hash table organizes by bench, the sets handle uniqueness, and we just need to find the maximum size at the end.

Solution Approach

The solution uses a hash table with sets to efficiently track unique students on each bench.

Step-by-step implementation:

1. Initialize the data structure: We create a defaultdict(set) called d. This is a hash table where:

   • Keys are bench IDs
   • Values are sets that will store unique student IDs
   • Using defaultdict(set) means if we access a bench ID that doesn't exist yet, it automatically creates an empty set for it

2. Process the student data: We iterate through each entry in the students array:

   for student_id, bench_id in students:
       d[bench_id].add(student_id)

   • For each [student_id, bench_id] pair, we add the student_id to the set corresponding to bench_id
   • The add() operation on a set ensures uniqueness - if the same student ID is added multiple times to the same bench's set, it only counts once

3. Find the maximum: After processing all entries, we need to find which bench has the most unique students:

   return max(map(len, d.values()))

   • d.values() gives us all the sets (one for each bench)
   • map(len, d.values()) applies the len function to each set, giving us the count of unique students per bench
   • max() returns the largest count among all benches

4. Handle edge case: The initial check if not students: return 0 handles the case where the input array is empty.

Time Complexity: O(n) where n is the number of entries in the students array, as we iterate through the array once and set operations are O(1) on average.

Space Complexity: O(n) in the worst case where all entries are unique student-bench combinations.

Example Walkthrough

Let's walk through a concrete example to illustrate how the solution works.

Input: students = [[1, 2], [3, 2], [1, 2], [4, 5], [5, 5], [1, 5]]

Step 1: Initialize the hash table We create an empty defaultdict(set) called d = {}

Step 2: Process each student-bench pair

• Process [1, 2]: Add student 1 to bench 2's set

  • d = {2: {1}}

• Process [3, 2]: Add student 3 to bench 2's set

  • d = {2: {1, 3}}

• Process [1, 2]: Add student 1 to bench 2's set (already exists, no change)

  • d = {2: {1, 3}}

• Process [4, 5]: Add student 4 to bench 5's set

  • d = {2: {1, 3}, 5: {4}}

• Process [5, 5]: Add student 5 to bench 5's set

  • d = {2: {1, 3}, 5: {4, 5}}

• Process [1, 5]: Add student 1 to bench 5's set

  • d = {2: {1, 3}, 5: {1, 4, 5}}

Step 3: Find the maximum number of unique students

• Bench 2 has 2 unique students: {1, 3}
• Bench 5 has 3 unique students: {1, 4, 5}
• Maximum = 3

Output: 3

Notice how student 1 appearing twice on bench 2 didn't increase the count for that bench, and how student 1 can be counted on both bench 2 and bench 5 since we're looking for the maximum per single bench, not across all benches.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the students array. This is because we iterate through the students list once to populate the dictionary, and then iterate through the dictionary values once to find the maximum. The max() function with map(len, d.values()) takes O(m) time where m is the number of unique benches, but since m ≤ n, the overall time complexity remains O(n).

The space complexity is O(n), where n is the length of the students array. In the worst case, each student sits on a different bench, resulting in a dictionary with n entries. Additionally, we store up to n student IDs across all sets in the dictionary. Therefore, the total space used is proportional to n.

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

Common Pitfalls

1. Not Handling Empty Input Correctly

A common mistake is forgetting to handle the edge case when the students array is empty. If you directly call max() on an empty sequence, Python will raise a ValueError.

Incorrect approach:

def maxStudentsOnBench(self, students: List[List[int]]) -> int:
    bench_to_students = defaultdict(set)
    for student_id, bench_id in students:
        bench_to_students[bench_id].add(student_id)
    return max(map(len, bench_to_students.values()))  # ValueError if students is empty!

Solution: Always check for empty input first, or use max() with a default value:

# Option 1: Explicit check (shown in original solution)
if not students:
    return 0

# Option 2: Use max with default parameter
return max(map(len, bench_to_students.values()), default=0)

2. Counting Duplicate Entries Instead of Unique Students

The most critical mistake is counting each entry separately instead of tracking unique students per bench. This happens when using a list or counter instead of a set.

Incorrect approach:

def maxStudentsOnBench(self, students: List[List[int]]) -> int:
    bench_counts = defaultdict(int)
    for student_id, bench_id in students:
        bench_counts[bench_id] += 1  # Wrong! Counts duplicates
    return max(bench_counts.values()) if bench_counts else 0

This would incorrectly return 3 for input [[1,2], [1,2], [3,2]] instead of 2.

Solution: Use a set to automatically handle uniqueness:

bench_to_students = defaultdict(set)
for student_id, bench_id in students:
    bench_to_students[bench_id].add(student_id)  # Set ensures uniqueness

3. Using Regular Dictionary Instead of defaultdict

Using a regular dictionary requires manual initialization of sets for new bench IDs, making the code more verbose and error-prone.

Less elegant approach:

bench_to_students = {}
for student_id, bench_id in students:
    if bench_id not in bench_to_students:
        bench_to_students[bench_id] = set()  # Manual initialization needed
    bench_to_students[bench_id].add(student_id)

Solution: Use defaultdict(set) for cleaner, more concise code that automatically initializes empty sets for new keys.