Watch the video solution for Maximum Students on a Single Bench, a easy level problem involving Array, Hash Table. This walkthrough by AlgorithmicIQ has 12 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: students = [[1,2],[2,2],[3,3],[1,3],[2,3]]
Output: 3
Explanation:
[1, 2].[1, 2, 3].Example 2:
Input: students = [[1,1],[2,1],[3,1],[4,2],[5,2]]
Output: 3
Explanation:
[1, 2, 3].[4, 5].Example 3:
Input: students = [[1,1],[1,1]]
Output: 1
Explanation:
Example 4:
Input: students = []
Output: 0
Explanation:
Constraints:
0 <= students.length <= 100students[i] = [student_id, bench_id]1 <= student_id <= 1001 <= bench_id <= 100Problem Overview: You receive a list representing which bench each student is sitting on. The goal is simple: determine the maximum number of students sitting on the same bench. In practice, this reduces to finding the highest frequency of any bench ID in the input array.
Approach 1: Brute Force Counting (O(n2) time, O(1) space)
Start by checking every student and counting how many other students share the same bench. For each index i, iterate through the entire array again and increment a counter whenever you see the same bench number. Track the maximum count across all iterations. This approach works because it directly compares each pair of entries, but the nested iteration makes it inefficient for large inputs. Time complexity is O(n2) and space complexity is O(1) since only a few counters are stored.
Approach 2: Hash Table Frequency Count (O(n) time, O(n) space)
The optimal approach counts how many times each bench appears using a hash map. Iterate through the array once and store the frequency of each bench in a map where the key is the bench number and the value is the number of students sitting there. Every time you update the count, compare it with the current maximum and update the result if needed. This eliminates repeated scans of the array and reduces the runtime to a single pass.
This technique is a classic frequency-count pattern commonly used in hash table problems. Each insertion and lookup in the map runs in average O(1) time, giving an overall time complexity of O(n). The space complexity is O(n) in the worst case if every student sits on a different bench. Since the input is simply iterated once, the logic stays clean and scalable.
You can implement this easily in languages like Python using dictionaries, Java with HashMap, C++ with unordered_map, or similar structures in Go, TypeScript, and Rust. The algorithm relies on simple iteration over the array while maintaining frequency counts.
Recommended for interviews: The hash table frequency approach is what interviewers expect. The brute force method demonstrates baseline reasoning but does not scale well. Recognizing that the problem reduces to counting occurrences of each bench—and applying a hash map to track frequencies—shows familiarity with common hash table patterns used across many interview problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Counting | O(n^2) | O(1) | Small inputs or when demonstrating the straightforward comparison approach |
| Hash Table Frequency Count | O(n) | O(n) | General case and interview settings where efficient frequency counting is required |