1349. Maximum Students Taking Exam - Solution

The problem

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

Students can see the answers of those sitting next to the left, right, upper left and upper right, but he cannot see the answers of the student sitting directly in front or behind him. Return the maximum number of students that can take the exam together without any cheating being possible.

Students must be placed in seats in good condition.

Example 1:

Input: seats = [["#",".","#","#",".","#"],
                [".","#","#","#","#","."],
                ["#",".","#","#",".","#"]]
Output: 4
Explanation: Teacher can place 4 students in available seats so they don't cheat on the exam.

Example 2:

Input: seats = [[".","#"],
                ["#","#"],
                ["#","."],
                ["#","#"],
                [".","#"]]
Output: 3
Explanation: Place all students in available seats.

Example 3:

Input: seats = [["#",".",".",".","#"],
                [".","#",".","#","."],
                [".",".","#",".","."],
                [".","#",".","#","."],
                ["#",".",".",".","#"]]
Output: 10
Explanation: Place students in available seats in column 1, 3 and 5.

Constraints:

seats contains only characters '.' and'#'.
m == seats.length
n == seats[i].length
1 <= m <= 8
1 <= n <= 8

Approach overview

Problem Overview: You receive a classroom matrix where '.' represents a usable seat and '#' represents a broken one. Students cannot sit next to each other horizontally or diagonally across rows because they could cheat. The goal is to place the maximum number of students while respecting these constraints.

Approach 1: Backtracking with Pruning (Exponential Time, O(2^(m*n)) time, O(m*n) space)

This approach tries every valid seating configuration. You recursively decide whether to place a student in each seat while checking cheating constraints: no left/right neighbor in the same row and no upper-left or upper-right neighbor from the previous row. Pruning removes branches early when a placement violates rules. While straightforward, the state space grows quickly for larger grids, making it impractical for worst‑case inputs.

Approach 2: Bitmask Dynamic Programming (O(m * 2^n * 2^n) time, O(m * 2^n) space)

This optimized approach models each row as a bitmask representing which seats contain students. First generate all valid row masks where no two students sit adjacent horizontally and broken seats are excluded. Then use dynamic programming across rows: for each row mask, iterate over all valid masks from the previous row and ensure diagonal cheating rules are satisfied using bit operations like (mask << 1) and (mask >> 1). The DP state dp[row][mask] stores the maximum students up to that row with the given configuration. Bit operations make compatibility checks constant time, which drastically reduces the search space.

This technique combines bit manipulation with row‑by‑row DP over the matrix. Because each row has at most 2^n configurations (with n ≤ 8 in constraints), the algorithm remains tractable even for multiple rows.

Recommended for interviews: Bitmask Dynamic Programming is the expected solution. Interviewers want to see that you can compress row states with bitmasks and validate constraints using bit shifts. Backtracking demonstrates understanding of the constraints, but the DP approach shows stronger algorithmic optimization skills.

Approach 1: Bitmask Dynamic Programming

This approach uses dynamic programming with bitmasks to represent the state of each row. You iterate through each row while keeping track of all allowed seat arrangements, updating possible arrangements for the subsequent rows. The idea is to maximize the number of students placed while satisfying the constraints (no students adjacent).

Python

def maxStudents(seats):
    m, n = len(seats), len(seats[0])
    dp = [-1] * (1 << n)
    dp[0] = 0
    for row in seats:
        validRows = []
        for i in range(1 << n):
            if all((i & (1 << j)) == 0 or row[j] == '.' for j in range(n)) and (i & (i >> 1)) == 0:
                validRows.append(i)
        newDp = [-1] * (1 << n)
        for newRow in validRows:
            population = bin(newRow).count('1')
            for oldRow in range(1 << n):
                if dp[oldRow] != -1 and (oldRow & (newRow >> 1)) == (oldRow & (newRow << 1)) == 0:
                    newDp[newRow] = max(newDp[newRow], dp[oldRow] + population)
        dp = newDp
    return max(dp)

C++

#include <vector>
#include <algorithm>
using namespace std;

int maxStudents(vector<vector<char>>& seats) {
    int m = seats.size(), n = seats[0].size();
    vector<int> dp(1 << n, -1);
    dp[0] = 0;
    for (const auto& row : seats) {
        vector<int> valid;
        for (int mask = 0; mask < (1 << n); ++mask) {
            bool isValid = true;
            for (int j = 0; j < n; ++j) 
                if ((mask & (1 << j)) && (row[j] == '#' || (mask & (1 << (j - 1))) || (mask & (1 << (j + 1))))) {
                    isValid = false;
                    break;
                }
            if (isValid) valid.push_back(mask);
        }
        vector<int> newDp(1 << n, -1);
        for (int newMask : valid) {
            int count = __builtin_popcount(newMask);
            for (int oldMask = 0; oldMask < (1 << n); ++oldMask) {
                if (dp[oldMask] != -1 && ((newMask & (oldMask >> 1)) == 0) && ((newMask & (oldMask << 1)) == 0))
                    newDp[newMask] = max(newDp[newMask], dp[oldMask] + count);
            }
        }
        dp = move(newDp);
    }
    return *max_element(dp.begin(), dp.end());
}

The solution involves creating a dynamic programming array where every state represents a valid seating arrangement in a row using a bitmask. For each row, compute all valid seating patterns and transition states by checking if placing students in the current row conflicts with the previous one. Maximize the count of seated students.

Complexity

Time complexity: O(m * 3^n), where m is the number of rows and n the number of columns because each row configuration can have up to 3^n states.
Space complexity: O(3^n), for storing the DP states.

Try this approach in the editor

Approach 2: Backtracking with Pruning

In this approach, use backtracking with pruning to maximize the number of placed students. You attempt to place a student in each seat and check for conflicts recursively, pruning invalid configurations early. Although slower than DP, this method works due to the constraints on m and n.

Java

public class Solution {
    private int maxCount = 0;

    public int maxStudents(char[][] seats) {
        int m = seats.length, n = seats[0].length;
        backtrack(seats, 0, 0, 0);
        return maxCount;
    }

    private void backtrack(char[][] seats, int row, int col, int count) {
        int m = seats.length, n = seats[0].length;
        if (row == m) {
            maxCount = Math.max(maxCount, count);
            return;
        }

        if (col == n) {
            backtrack(seats, row + 1, 0, count);
            return;
        }

        if (seats[row][col] == '.') {
            if (isSafe(seats, row, col)) {
                seats[row][col] = 'S'; // Place student
                backtrack(seats, row, col + 1, count + 1);
                seats[row][col] = '.'; // Backtrack
            }
        }
        backtrack(seats, row, col + 1, count);
    }

    private boolean isSafe(char[][] seats, int row, int col) {
        int m = seats.length, n = seats[0].length;
        if (col > 0 && seats[row][col - 1] == 'S') return false; // left
        if (row > 0 && col > 0 && seats[row - 1][col - 1] == 'S') return false; // upper-left
        if (row > 0 && col < n - 1 && seats[row - 1][col + 1] == 'S') return false; // upper-right
        if (col < n - 1 && seats[row][col + 1] == 'S') return false; // right
        return true;
    }
}

public class Solution {
    private int maxCount = 0;
    public int MaxStudents(char[][] seats) {
        Backtrack(seats, 0, 0, 0);
        return maxCount;
    }

    private void Backtrack(char[][] seats, int row, int col, int count) {
        int m = seats.Length, n = seats[0].Length;
        if (row == m) {
            maxCount = Math.Max(maxCount, count);
            return;
        }

        if (col == n) {
            Backtrack(seats, row + 1, 0, count);
            return;
        }

        if (seats[row][col] == '.') {
            if (IsSafe(seats, row, col)) {
                seats[row][col] = 'S';
                Backtrack(seats, row, col + 1, count + 1);
                seats[row][col] = '.';
            }
        }
        Backtrack(seats, row, col + 1, count);
    }

    private bool IsSafe(char[][] seats, int row, int col) {
        int m = seats.Length, n = seats[0].Length;
        if (col > 0 && seats[row][col - 1] == 'S') return false;
        if (row > 0 && col > 0 && seats[row - 1][col - 1] == 'S') return false;
        if (row > 0 && col < n - 1 && seats[row - 1][col + 1] == 'S') return false;
        if (col < n - 1 && seats[row][col + 1] == 'S') return false;
        return true;
    }
}

The backtracking algorithm places a student at each position if possible. It checks left, right, upper-left, and upper-right neighbors to avoid cheating. If a valid position for a student is found, it records the result and continues. Using a recursive function, the solution explores valid configurations and prunes branches where cheating could occur.

Complexity

Time complexity: O(2^(m*n)), as each position has two possibilities: occupied or not. However, pruning significantly reduces the actual search space.
Space complexity: O(m * n), which is the recursion call stack size.

Try this approach in the editor

Approach 3: State Compression + Memoization Search

We notice that each seat has two states: selectable and non-selectable. Therefore, we can use a binary number to represent the seat state of each row, where 1 represents selectable, and 0 represents non-selectable. For example, for the first row in Example 1, we can represent it as 010010. Therefore, we convert the initial seats into a one-dimensional array ss, where ss[i] represents the seat state of the ith row.

Next, we design a function dfs(seat, i), which represents the maximum number of students that can be accommodated starting from the ith row, and the seat state of the current row is seat.

We can enumerate all the seat selection states mask of the ith row, and judge whether mask meets the following conditions:

The state mask cannot select seats outside of seat;
The state mask cannot select adjacent seats.

If the conditions are met, we calculate the number of seats selected in the current row cnt. If it is the last row, update the return value of the function, that is, ans = max(ans, cnt). Otherwise, we continue to recursively solve the maximum number of the next row. The seat state of the next row is nxt = ss[i + 1], and we need to exclude the left and right sides of the selected seats in the current row. Then we recursively solve the maximum number of the next row, that is, ans = max(ans, cnt + dfs(nxt, i + 1)).

Finally, we return ans as the return value of the function.

To avoid repeated calculations, we can use memoization search to save the return value of the function dfs(seat, i) in a two-dimensional array f, where f[seat][i] represents the maximum number of students that can be accommodated starting from the ith row, and the seat state of the current row is seat.

The time complexity is O(4^n times n times m), and the space complexity is O(2^n times m). Where m and n are the number of rows and columns of the seats, respectively.

TypeScript

function maxStudents(seats: string[][]): number {
    const m: number = seats.length;
    const n: number = seats[0].length;
    const ss: number[] = Array(m).fill(0);
    const f: number[][] = Array.from({ length: 1 << n }, () => Array(m).fill(-1));
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (seats[i][j] === '.') {
                ss[i] |= 1 << j;
            }
        }
    }

    const dfs = (seat: number, i: number): number => {
        if (f[seat][i] !== -1) {
            return f[seat][i];
        }
        let ans: number = 0;
        for (let mask = 0; mask < 1 << n; ++mask) {
            if ((seat | mask) !== seat || (mask & (mask << 1)) !== 0) {
                continue;
            }
            const cnt: number = mask.toString(2).split('1').length - 1;
            if (i === m - 1) {
                ans = Math.max(ans, cnt);
            } else {
                let nxt: number = ss[i + 1];
                nxt &= ~(mask >> 1);
                nxt &= ~(mask << 1);
                ans = Math.max(ans, cnt + dfs(nxt, i + 1));
            }
        }
        return (f[seat][i] = ans);
    };
    return dfs(ss[0], 0);
}

func maxStudents(seats [][]byte) int {
	m, n := len(seats), len(seats[0])
	ss := make([]int, m)
	f := make([][]int, 1<<n)
	for i, seat := range seats {
		for j, c := range seat {
			if c == '.' {
				ss[i] |= 1 << j
			}
		}
	}
	for i := range f {
		f[i] = make([]int, m)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	var dfs func(int, int) int
	dfs = func(seat, i int) int {
		if f[seat][i] != -1 {
			return f[seat][i]
		}
		ans := 0
		for mask := 0; mask < 1<<n; mask++ {
			if (seat|mask) != seat || (mask&(mask<<1)) != 0 {
				continue
			}
			cnt := bits.OnesCount(uint(mask))
			if i == m-1 {
				ans = max(ans, cnt)
			} else {
				nxt := ss[i+1] & ^(mask >> 1) & ^(mask << 1)
				ans = max(ans, cnt+dfs(nxt, i+1))
			}
		}
		f[seat][i] = ans
		return ans
	}
	return dfs(ss[0], 0)
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Bitmask Dynamic Programming	Time complexity: O(m * 3^n), where m is the number of rows and n the number of columns because each row configuration can have up to 3^n states. Space complexity: O(3^n), for storing the DP states.
Backtracking with Pruning	Time complexity: O(2^(mn)), as each position has two possibilities: occupied or not. However, pruning significantly reduces the actual search space. Space complexity:* O(m * n), which is the recursion call stack size.
State Compression + Memoization Search	–

Complexity analysis

Approach	Time	Space	When to Use
Backtracking with Pruning	O(2^(m*n))	O(m*n)	Good for understanding constraints or very small grids
Bitmask Dynamic Programming	O(m * 2^n * 2^n)	O(m * 2^n)	Optimal solution for interview settings and typical constraints

Frequently asked questions

Is Maximum Students Taking Exam easy or hard?

Maximum Students Taking Exam is classified as a Hard problem. It requires combining matrix traversal, bitmask state compression, and dynamic programming to efficiently evaluate valid seating arrangements.

Maximum Students Taking Exam Python/Java solution

Common implementations use Bitmask Dynamic Programming. Python and C++ versions typically iterate through valid seat masks and update DP states per row, while Java implementations sometimes demonstrate the backtracking approach with pruning.

How to solve Maximum Students Taking Exam in O(n)?

The problem cannot be solved in strict O(n) time because you must evaluate seating combinations per row. The practical optimal method uses Bitmask Dynamic Programming with complexity O(m * 2^n * 2^n), which is efficient given the small column limit.

What is the best approach for Maximum Students Taking Exam?

Bitmask Dynamic Programming is the best approach. Each row is represented as a bitmask of seated students, and DP transitions check compatibility with the previous row using bit shifts to enforce diagonal constraints. This reduces the search space to O(m * 2^n * 2^n).

Is Maximum Students Taking Exam asked at Google/Amazon/Meta?

Maximum Students Taking Exam is a classic hard problem involving bitmask DP and constraint checking, which appears in interview preparation lists for companies like Google and Amazon. It tests advanced state compression and dynamic programming skills.

What data structure is used in Maximum Students Taking Exam?

The solution relies on bitmasks to represent row seating configurations and a dynamic programming table to store the best result for each row state. Bit operations allow constant‑time checks for horizontal and diagonal cheating conflicts.

What is the time complexity of Maximum Students Taking Exam?

The optimal Bitmask DP solution runs in O(m * 2^n * 2^n) time where m is the number of rows and n is the number of columns. Space complexity is O(m * 2^n) for storing DP states. The exponential factor is manageable because n is typically ≤ 8.

Maximum Students Taking Exam solution and explanation

The problem

Approach overview

Approach 1: Bitmask Dynamic Programming

Approach 2: Backtracking with Pruning

Approach 3: State Compression + Memoization Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximum Students Taking Exam solution and explanation

The problem

Approach overview

Approach 1: Bitmask Dynamic Programming

Approach 2: Backtracking with Pruning

Approach 3: State Compression + Memoization Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems