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}\).

Python3JavaC++GoTypeScriptRust

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

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;
    }
};

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
    }
}

3450. Maximum Students on a Single Bench 🔒

Description

Solutions

Solution 1: Hash Table

Comments