Maximum Students on a Single Bench - Solution & Explanation

Problem 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(n²) 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(n²) 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.