LeetCode 3450 - Maximum Students on a Single Bench

The problem provides a list of student-seat assignments, where each entry has the form [studentid, benchid]. Each pair indicates that a particular student is sitting on a particular bench.

leetcodeeasyarrayhash-table

LeetCode Problem 3450

Difficulty: 🟢 Easy
Topics: Array, Hash Table

Solution

Problem Understanding

The problem provides a list of student-seat assignments, where each entry has the form [student_id, bench_id]. Each pair indicates that a particular student is sitting on a particular bench.

The goal is to determine which bench has the largest number of unique students sitting on it and return that count.

The important detail is that a student may appear multiple times for the same bench in the input. These duplicate records should only be counted once. For example, if the input contains [[1,1], [1,1], [1,1]], bench 1 still has only one unique student.

The input is a two-dimensional array where:

  • student_id identifies a student.
  • bench_id identifies a bench.

The output is a single integer representing the maximum number of distinct students assigned to any one bench.

The constraints are very small:

  • At most 100 records exist.
  • Student IDs range from 1 to 100.
  • Bench IDs range from 1 to 100.

Because the input size is tiny, even less efficient approaches would work. However, it is still useful to design a clean and optimal solution.

Several edge cases are important:

  • The input may be empty, in which case the answer is 0.
  • A student may appear multiple times on the same bench and must only be counted once.
  • Multiple benches may contain the same student.
  • There may be only one bench.
  • There may be only one unique student across all records.

Approaches

Brute Force

A straightforward approach is to examine every bench separately.

For each possible bench, we could scan the entire input and collect all students assigned to that bench into a set. After finishing the scan, we compute the size of that set and update the maximum answer.

This approach is correct because the set automatically removes duplicates, ensuring that each student is counted only once per bench. By evaluating every bench, we eventually discover the bench with the largest number of unique students.

However, this repeatedly scans the input for each bench. If there are B benches and N records, the time complexity becomes O(B × N).

Optimal Approach

The key observation is that we can build the student sets for all benches in a single pass.

We maintain a hash map where:

  • The key is a bench ID.
  • The value is a set containing all unique students assigned to that bench.

As we process each [student_id, bench_id] pair, we insert the student into that bench's set. Since sets automatically eliminate duplicates, repeated appearances of the same student on the same bench do not affect the count.

After processing all records, we simply examine every set and return the largest size.

This avoids repeatedly scanning the input and processes every record only once.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(B × N) O(N) Scan all records separately for each bench
Optimal O(N) O(N) Build bench-to-students mapping in one pass

Algorithm Walkthrough

  1. Create an empty hash map called bench_students.

The keys will be bench IDs, and the values will be sets of student IDs. A hash map provides efficient access to each bench, while a set ensures uniqueness. 2. Iterate through every record in students.

For each pair [student_id, bench_id], check whether the bench already exists in the map. If not, create an empty set for it. 3. Insert the student ID into the corresponding bench's set.

If the same student appears multiple times for the same bench, the set automatically keeps only one copy. 4. After processing all records, initialize the answer to 0. 5. Iterate through all sets stored in the hash map.

For each set, compute its size and update the answer if this size is larger than the current maximum. 6. Return the maximum value found.

If the input was empty, the hash map remains empty and the answer stays 0.

Why it works

For every bench, the algorithm stores exactly the set of students assigned to that bench. Because sets contain unique elements, duplicate records do not increase the count. Therefore, the size of each set equals the number of unique students sitting on that bench. Taking the maximum size across all benches yields exactly the required answer.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def maxStudentsOnBench(self, students: List[List[int]]) -> int:
        bench_students = defaultdict(set)

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

        max_students = 0

        for student_set in bench_students.values():
            max_students = max(max_students, len(student_set))

        return max_students

The implementation closely follows the algorithm.

A defaultdict(set) is used so that each bench automatically receives an empty set when first encountered. During the single pass through the input, each student is added to the set associated with their bench.

Once all records have been processed, every bench maps to a set of unique students. The final loop computes the largest set size and returns it. If the input is empty, the loop never updates max_students, so the function correctly returns 0.

Go Solution

func maxStudentsOnBench(students [][]int) int {
	benchStudents := make(map[int]map[int]struct{})

	for _, record := range students {
		studentID := record[0]
		benchID := record[1]

		if _, exists := benchStudents[benchID]; !exists {
			benchStudents[benchID] = make(map[int]struct{})
		}

		benchStudents[benchID][studentID] = struct{}{}
	}

	maxStudents := 0

	for _, studentSet := range benchStudents {
		if len(studentSet) > maxStudents {
			maxStudents = len(studentSet)
		}
	}

	return maxStudents
}

The Go implementation uses a map from bench IDs to another map that acts as a set. Since Go does not provide a built-in set type, map[int]struct{} is the standard approach. The empty struct consumes no storage beyond the map entry itself.

An empty or nil input slice is handled naturally because the loops simply execute zero iterations, leaving the answer at 0.

Worked Examples

Example 1

Input

[[1,2],[2,2],[3,3],[1,3],[2,3]]

Processing:

Step Record bench_students
1 [1,2] {2: {1}}
2 [2,2] {2: {1,2}}
3 [3,3] {2: {1,2}, 3: {3}}
4 [1,3] {2: {1,2}, 3: {1,3}}
5 [2,3] {2: {1,2}, 3: {1,2,3}}

Final set sizes:

Bench Unique Students Count
2 {1,2} 2
3 {1,2,3} 3

Maximum = 3

Example 2

Input

[[1,1],[2,1],[3,1],[4,2],[5,2]]

Processing:

Step Record bench_students
1 [1,1] {1:{1}}
2 [2,1] {1:{1,2}}
3 [3,1] {1:{1,2,3}}
4 [4,2] {1:{1,2,3}, 2:{4}}
5 [5,2] {1:{1,2,3}, 2:{4,5}}

Final counts:

Bench Count
1 3
2 2

Maximum = 3

Example 3

Input

[[1,1],[1,1]]

Processing:

Step Record bench_students
1 [1,1] {1:{1}}
2 [1,1] {1:{1}}

The duplicate insertion does not change the set.

Final count:

Bench Count
1 1

Maximum = 1

Example 4

Input

[]

No records are processed.

Variable Value
bench_students {}
max_students 0

Answer = 0

Complexity Analysis

Measure Complexity Explanation
Time O(N) Each record is processed exactly once
Space O(N) In the worst case every record contributes a unique student-bench relationship

The algorithm performs a single pass over the input and each hash map or set operation is expected O(1). Therefore the total running time is linear in the number of records. The storage requirement is also linear because every unique student assignment may need to be stored in a set.

Test Cases

from typing import List

s = Solution()

assert s.maxStudentsOnBench([[1,2],[2,2],[3,3],[1,3],[2,3]]) == 3  # example 1
assert s.maxStudentsOnBench([[1,1],[2,1],[3,1],[4,2],[5,2]]) == 3  # example 2
assert s.maxStudentsOnBench([[1,1],[1,1]]) == 1  # duplicate student on same bench
assert s.maxStudentsOnBench([]) == 0  # empty input

assert s.maxStudentsOnBench([[1,1]]) == 1  # single record
assert s.maxStudentsOnBench([[1,1],[2,1],[3,1]]) == 3  # one bench only
assert s.maxStudentsOnBench([[1,1],[1,2],[1,3]]) == 1  # same student on multiple benches
assert s.maxStudentsOnBench([[1,1],[2,1],[2,1],[3,1]]) == 3  # duplicates mixed with unique students
assert s.maxStudentsOnBench([[1,1],[2,2],[3,3]]) == 1  # every bench has one student
assert s.maxStudentsOnBench([[1,1],[2,1],[3,2],[4,2]]) == 2  # tie between benches

# maximum constraint style test
students = [[i, 1] for i in range(1, 101)]
assert s.maxStudentsOnBench(students) == 100  # 100 unique students on one bench

Test Summary

Test Why
[[1,2],[2,2],[3,3],[1,3],[2,3]] Standard multi-bench example
[[1,1],[2,1],[3,1],[4,2],[5,2]] Largest bench appears first
[[1,1],[1,1]] Duplicate entries should count once
[] Empty input
[[1,1]] Smallest non-empty input
[[1,1],[2,1],[3,1]] Single bench case
[[1,1],[1,2],[1,3]] Same student across multiple benches
[[1,1],[2,1],[2,1],[3,1]] Mixed duplicates and unique values
[[1,1],[2,2],[3,3]] All benches have equal count
[[1,1],[2,1],[3,2],[4,2]] Tie for maximum
100 unique students on one bench Stress test near constraint limit

Edge Cases

Empty Input

When students is empty, there are no benches and no students. A common bug is attempting to compute the maximum over an empty collection, which may raise an exception in some languages. This implementation initializes the answer to 0 and only updates it while iterating through existing benches, so it correctly returns 0.

Duplicate Student Records on the Same Bench

An input such as [[1,1],[1,1],[1,1]] contains multiple identical records. A naive implementation that simply counts records would incorrectly return 3. By storing student IDs in a set, duplicates are automatically removed, and the bench correctly contributes only one unique student.

Same Student Appearing on Multiple Benches

A student can appear on different benches, such as [[1,1],[1,2],[1,3]]. The uniqueness requirement applies separately to each bench, not globally. The implementation maintains an independent set for every bench, ensuring that the same student is counted once on each bench where they appear.

Multiple Benches Tied for Maximum

Two or more benches may have the same highest number of unique students. Since the problem asks only for the maximum count, not the bench itself, the algorithm simply tracks the largest set size encountered. Ties are handled naturally because the maximum value remains unchanged when an equal count is found.