Welcome to Subscribe On Youtube

3450. Maximum Students on a Single Bench 🔒

Description

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

Solutions

Solution 1: Hash Table

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 $\textit{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 $\textit{students}$.

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

• class Solution {
      public int maxStudentsOnBench(int[][] students) {
          Map<Integer, Set<Integer>> d = new HashMap<>();
          for (var e : students) {
              int studentId = e[0], benchId = e[1];
              d.computeIfAbsent(benchId, k -> new HashSet<>()).add(studentId);
          }
          int ans = 0;
          for (var s : d.values()) {
              ans = Math.max(ans, s.size());
          }
          return ans;
      }
  }
  
  

• class Solution {
  public:
      int maxStudentsOnBench(vector<vector<int>>& students) {
          unordered_map<int, unordered_set<int>> d;
          for (const auto& e : students) {
              int studentId = e[0], benchId = e[1];
              d[benchId].insert(studentId);
          }
          int ans = 0;
          for (const auto& s : d) {
              ans = max(ans, (int) s.second.size());
          }
          return ans;
      }
  };
  
  

• class Solution:
      def maxStudentsOnBench(self, students: List[List[int]]) -> int:
          if not students:
              return 0
          d = defaultdict(set)
          for student_id, bench_id in students:
              d[bench_id].add(student_id)
          return max(map(len, d.values()))
  
  

• func maxStudentsOnBench(students [][]int) (ans int) {
  	d := make(map[int]map[int]struct{})
  	for _, e := range students {
  		studentId, benchId := e[0], e[1]
  		if _, exists := d[benchId]; !exists {
  			d[benchId] = make(map[int]struct{})
  		}
  		d[benchId][studentId] = struct{}{}
  	}
  	for _, s := range d {
  		ans = max(ans, len(s))
  	}
  	return
  }
  
  

• function maxStudentsOnBench(students: number[][]): number {
      const d: Map<number, Set<number>> = new Map();
      for (const [studentId, benchId] of students) {
          if (!d.has(benchId)) {
              d.set(benchId, new Set());
          }
          d.get(benchId)?.add(studentId);
      }
      let ans = 0;
      for (const s of d.values()) {
          ans = Math.max(ans, s.size);
      }
      return ans;
  }
  
  

• use std::collections::{HashMap, HashSet};
  
  impl Solution {
      pub fn max_students_on_bench(students: Vec<Vec<i32>>) -> i32 {
          let mut d: HashMap<i32, HashSet<i32>> = HashMap::new();
          for e in students {
              let student_id = e[0];
              let bench_id = e[1];
              d.entry(bench_id)
                  .or_insert_with(HashSet::new)
                  .insert(student_id);
          }
          let mut ans = 0;
          for s in d.values() {
              ans = ans.max(s.len() as i32);
          }
          ans
      }
  }
  
  

All Problems

All Solutions