We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Students on a Single Bench

Number: 3787

Difficulty: Easy

Paid? Yes

Companies: N/A

Problem Description

Given a list of student bench assignments where each element is of the form [student_id, bench_id], determine the maximum number of unique students sitting on any bench. Note that a student may appear more than once on the same bench, but they should only be counted once. If the input list is empty, return 0.

Key Insights

  • Use a dictionary/hash map where each key is a bench_id and the value is a set of unique student_ids.
  • By utilizing a set, duplicate student entries for the same bench are automatically ignored.
  • Iterate over the dictionary's values to compute the size (i.e., number of unique students) for each bench and determine the maximum.
  • Handle the edge case when the input is empty by returning 0.

Space and Time Complexity

Time Complexity: O(n), where n is the number of student records. Space Complexity: O(n), since in the worst case every student record is unique and stored in the map.

Solution

We solve this problem by iterating through the list of student records and building a mapping from bench_id to a set of student_ids. This ensures each student is counted only once per bench. After constructing this map, we iterate over its values to find the bench with the maximum number of unique students.

Code Solutions

Below are code solutions with detailed line-by-line comments in Python, JavaScript, C++, and Java.

# Function to calculate maximum number of unique students on a bench
def max_unique_students(students):
    # Create a dictionary mapping bench_id to a set of student_ids
    bench_students = {}
    
    # Iterate over each student record [student_id, bench_id]
    for student_id, bench_id in students:
        # If bench_id is not already a key in the dictionary, initialize with an empty set
        if bench_id not in bench_students:
            bench_students[bench_id] = set()
        # Add the student_id to the set corresponding to the bench_id
        bench_students[bench_id].add(student_id)
    
    # Initialize max_count to 0
    max_count = 0
    
    # Iterate over each set of students in the dictionary
    for students_set in bench_students.values():
        # Update max_count if the current set's size is larger
        max_count = max(max_count, len(students_set))
    
    # Return the maximum count of unique students on any bench
    return max_count

# Example usage:
print(max_unique_students([[1,2],[2,2],[3,3],[1,3],[2,3]]))  # Expected output: 3
← Back to All Questions