Maximum Students on a Single Bench

Maximum Students on a Single Bench - Problem

You are given a 2D integer array students, where students[i] = [student_id, bench_id] represents that student student_id is sitting on 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.

Input & Output

Example 1 — Basic Case

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

› Output: 2

💡 Note: Bench 1 has students {1, 2} (2 unique), Bench 2 has students {3, 4} (2 unique), Bench 3 has student {5} (1 unique). Maximum is 2.

Example 2 — Empty Array

$ Input: students = []

› Output: 0

💡 Note: No students present, return 0.

Example 3 — All Same Bench

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

› Output: 3

💡 Note: All students sit on bench 5. Unique students are {1, 2, 3}, so return 3.

Constraints

0 ≤ students.length ≤ 10⁵
students[i].length == 2
1 ≤ student_id, bench_id ≤ 10⁵

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 f Facebook 8

The key insight is to use a hash map to group students by bench and count unique students per bench. The optimal approach uses frequency counting with hash maps in a single pass. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map - One Pass Frequency Count	O(n)	O(n)	Use nested hash maps to count unique students per bench in one pass
Brute Force - Check Each Bench Separately	O(n²)	O(n)	For each bench, iterate through all entries to count unique students

Hash Map - One Pass Frequency Count — Algorithm Steps

Step 1: Create hash map: bench_id → set of student_ids
Step 2: Iterate through students array once, adding to appropriate sets
Step 3: Find bench with maximum set size

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Create empty hash map: bench_id → set of students

Single Pass

For each student, add to their bench's set

Result

Find bench with largest set size

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_BENCHES 1000
#define MAX_STUDENTS_PER_BENCH 1000

struct BenchData {
    int benchId;
    int students[MAX_STUDENTS_PER_BENCH];
    int studentCount;
};

int solution(int students[][2], int n) {
    if (n == 0) return 0;
    
    struct BenchData benches[MAX_BENCHES];
    int benchCount = 0;
    
    // Single pass: group students by bench
    for (int i = 0; i < n; i++) {
        int studentId = students[i][0];
        int benchId = students[i][1];
        
        // Find or create bench
        int benchIndex = -1;
        for (int j = 0; j < benchCount; j++) {
            if (benches[j].benchId == benchId) {
                benchIndex = j;
                break;
            }
        }
        
        if (benchIndex == -1) {
            benchIndex = benchCount++;
            benches[benchIndex].benchId = benchId;
            benches[benchIndex].studentCount = 0;
        }
        
        // Add student if not already present
        int found = 0;
        for (int j = 0; j < benches[benchIndex].studentCount; j++) {
            if (benches[benchIndex].students[j] == studentId) {
                found = 1;
                break;
            }
        }
        
        if (!found) {
            benches[benchIndex].students[benches[benchIndex].studentCount++] = studentId;
        }
    }
    
    // Find bench with maximum unique students
    int maxStudents = 0;
    for (int i = 0; i < benchCount; i++) {
        if (benches[i].studentCount > maxStudents) {
            maxStudents = benches[i].studentCount;
        }
    }
    
    return maxStudents;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int students[1000][2];
    int n = 0;
    
    if (strcmp(line, "[]\n") == 0) {
        printf("0\n");
        return 0;
    }
    
    // Simple parsing for [[a,b],[c,d],...] format
    char* ptr = line + 1; // Skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            students[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++; // Skip comma
            students[n][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++; // Skip ]
            n++;
        } else {
            ptr++;
        }
    }
    
    printf("%d\n", solution(students, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the students array, hash map operations are O(1)

✓ Linear Growth

Space Complexity

O(n)

Hash map stores all unique (student, bench) pairs in worst case

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~8 min Avg. Time

256 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map - One Pass Frequency Count — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler