Problem

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.

Examples

Example 1

1
2
3
4
5
6
7
8
9
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

1
2
3
4
5
6
7
8
9
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

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

Output: 1

Explanation:

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

Solution

Method 1 – Hash Map for Counting

Intuition

To find the maximum number of students on a single bench, count the frequency of each bench number in the array. The answer is the highest frequency found.

Approach

  1. Use a hash map (dictionary) to count how many times each bench number appears in the array.
  2. The answer is the maximum value in the hash map.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int maximumStudents(vector<int>& benches) {
        unordered_map<int, int> cnt;
        int ans = 0;
        for (int b : benches) {
            ans = max(ans, ++cnt[b]);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int maximumStudents(int[] benches) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int ans = 0;
        for (int b : benches) {
            cnt.put(b, cnt.getOrDefault(b, 0) + 1);
            ans = Math.max(ans, cnt.get(b));
        }
        return ans;
    }
}
1
2
3
4
5
class Solution:
    def maximumStudents(self, benches: list[int]) -> int:
        from collections import Counter
        cnt = Counter(benches)
        return max(cnt.values())

Complexity

  • ⏰ Time complexity: O(n), where n is the number of students (length of benches array), since we count each bench once.
  • 🧺 Space complexity: O(n), for the hash map storing counts.