Skip to content

3450. Maximum Students on a Single Bench πŸ”’

Description

None

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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
    }
}

Comments