Skip to main content
Talentd

Maximum Students on a Single Bench - Solution & Explanation

EasyPremiumFree on FleetCodeArrayHash Table8 min read
Practice this problem

Problem Statement

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:

  • Bench 2 has two unique students: [1, 2].
  • Bench 3 has three unique students: [1, 2, 3].
  • The maximum number of unique students on a single bench is 3.

Example 2:

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

Output: 3

Explanation:

  • Bench 1 has three unique students: [1, 2, 3].
  • Bench 2 has two unique students: [4, 5].
  • The maximum number of unique students on a single bench is 3.

Example 3:

Input: students = [[1,1],[1,1]]

Output: 1

Explanation:

  • The maximum number of unique students on a single bench is 1.

Example 4:

Input: students = []

Output: 0

Explanation:

  • Since no students are present, the output is 0.

 

Constraints:

  • 0 <= students.length <= 100
  • students[i] = [student_id, bench_id]
  • 1 <= student_id <= 100
  • 1 <= bench_id <= 100

Approach Overview

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(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.

Solution

We use a hash table d to store the students on each bench, where the key is the bench number and the value is a set containing the student IDs on that bench.

Traverse the student array students and store the student IDs and bench numbers in the hash table d.

Finally, we traverse the values of the hash table d and take the maximum size of the sets, which is the maximum number of different students on a single bench.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the student array students.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force CountingO(n^2)O(1)Small inputs or when demonstrating the straightforward comparison approach
Hash Table Frequency CountO(n)O(n)General case and interview settings where efficient frequency counting is required

Video Solution

Leetcode 3450 Maximum Students on a Single Bench • AlgorithmicIQ • 12 views views

Frequently Asked Questions

Is Maximum Students on a Single Bench easy or hard?
Maximum Students on a Single Bench is typically classified as an Easy problem. The solution relies on a basic frequency-count technique with a hash table and a single pass through the array.
Maximum Students on a Single Bench Python/Java solution
In Python, use a dictionary to track frequencies while iterating through the array. In Java, use a HashMap<Integer, Integer> to store and update counts. Both implementations run in O(n) time and O(n) space using the same frequency-count pattern.
How to solve Maximum Students on a Single Bench in O(n)?
Use a hash map where the key is the bench number and the value is the number of students sitting there. Iterate through the array, increment the count for the current bench, and update the maximum frequency seen so far. This single-pass counting approach achieves O(n) time complexity.
What is the best approach for Maximum Students on a Single Bench?
The best approach uses a hash table to count how many times each bench number appears. Iterate through the array once, update the frequency in a map, and track the maximum count. This method runs in O(n) time with O(n) space and is the standard interview solution.
Is Maximum Students on a Single Bench asked at Google/Amazon/Meta?
Frequency counting problems using hash tables appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact question may vary, the underlying pattern—tracking element frequencies efficiently—is a common interview topic.
What data structure is used in Maximum Students on a Single Bench?
The core data structure is a hash table (or hash map). It stores each bench number as a key and the number of students sitting on that bench as the value, enabling constant-time updates and lookups during iteration.
What is the time complexity of Maximum Students on a Single Bench?
The optimal solution runs in O(n) time because the array is scanned once and each hash map operation is O(1) on average. A naive brute force approach that compares each student with every other student takes O(n^2) time.

Ready to solve this problem?

Practice Maximum Students on a Single Bench with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays