Maximum Students Taking Exam - Practice Coding Problems

Maximum Students Taking Exam - Problem

Given an m × n matrix seats that represents seat distributions in a classroom. If a seat is broken, it is denoted by '#' character, otherwise it is denoted by '.' character.

Students can see the answers of those sitting next to them on the left, right, upper left and upper right, but they cannot see the answers of students sitting directly in front or behind them.

Return the maximum number of students that can take the exam together without any cheating being possible.

Note: Students must be placed in seats that are in good condition (marked with '.').

Input & Output

Example 1 — Basic Case

$ Input: seats = [[".","#"],["#","#"],["#","."],["#","#"],[".","#"]]

› Output: 1

💡 Note: Only one student can be placed at seats[0][0] or seats[2][1] or seats[4][0] without any cheating possibility

Example 2 — Multiple Students

$ Input: seats = [[".",".","."],[".",".","."],[".",".","."]]

› Output: 4

💡 Note: Students can be placed at (0,0), (0,2), (2,0), (2,2) in a checkerboard pattern to avoid cheating

Example 3 — All Broken Seats

$ Input: seats = [["#","#"],["#","#"]]

› Output: 0

💡 Note: No students can be placed since all seats are broken

Constraints

1 ≤ seats.length ≤ 8
1 ≤ seats[r].length ≤ 8
seats[r][c] is either '.' or '#'

Visualization

Tap to expand

Understanding the Visualization

Input

Classroom with available (.) and broken (#) seats

Constraint

Students can cheat diagonally and sideways

Solution

Place maximum students without cheating

Key Takeaway

🎯 Key Insight: Use bitmask DP to efficiently track valid seating arrangements row by row

Asked in

G Google 15 f Facebook 12 M Microsoft 8

The key insight is that students can only cheat diagonally and sideways, not forward/backward. Best approach uses bitmask dynamic programming to represent row states and check valid transitions. Time: O(m × 4^n), Space: O(2^n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Backtracking	O(2^(m×n))	O(m×n)	Try all possible seating combinations and find the maximum valid arrangement
Dynamic Programming with Bitmask	O(m × 4^n)	O(2^n)	Use bitmask DP to represent row states and build solution row by row

Brute Force with Backtracking — Algorithm Steps

Enumerate all possible seating arrangements
For each arrangement, check if any student can cheat
Return the maximum valid arrangement size

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Try all possible ways to place students

Validate

Check if arrangement prevents cheating

Track

Keep maximum valid arrangement

Code -

solution.c — C

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

int maxStudents = 0;
int m, n;
char seats[10][10];
int arrangement[10][10];

int isValidArrangement() {
    int directions[4][2] = {{-1, -1}, {-1, 1}, {0, -1}, {0, 1}};
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (arrangement[i][j] == 1) {
                for (int d = 0; d < 4; d++) {
                    int nr = i + directions[d][0];
                    int nc = j + directions[d][1];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && arrangement[nr][nc] == 1) {
                        return 0;
                    }
                }
            }
        }
    }
    return 1;
}

void backtrack(int pos, int count) {
    if (pos == m * n) {
        if (isValidArrangement()) {
            if (count > maxStudents) {
                maxStudents = count;
            }
        }
        return;
    }
    
    int row = pos / n, col = pos % n;
    backtrack(pos + 1, count);
    
    if (seats[row][col] == '.') {
        arrangement[row][col] = 1;
        backtrack(pos + 1, count + 1);
        arrangement[row][col] = 0;
    }
}

int solution() {
    maxStudents = 0;
    memset(arrangement, 0, sizeof(arrangement));
    backtrack(0, 0);
    return maxStudents;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON manually
    m = 0; n = 0;
    int i = 1;
    while (line[i] != '\0' && line[i] != ']') {
        if (line[i] == '[') {
            int j = 0;
            i++;
            while (line[i] != ']') {
                if (line[i] == '"') {
                    i++;
                    seats[m][j] = line[i];
                    j++;
                    i++;
                }
                i++;
            }
            if (n == 0) n = j;
            m++;
        }
        i++;
    }
    
    printf("%d\n", solution());
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^(m×n))

For each seat, we try placing or not placing a student, leading to 2^(m×n) combinations

✓ Linear Growth

Space Complexity

O(m×n)

Recursion stack depth can go up to m×n levels

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~35 min Avg. Time

892 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

Brute Force with Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler