#1349

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Students Taking Exam

Calculate the maximum number of students who can take an exam without cheating using state transition dynamic programming on seat arrangements.

array dynamic programming bit manipulation matrix bitmask

Problem Statement

You are given a m x n matrix seats representing a classroom where '#' indicates a broken seat and '.' indicates a usable seat. Students can only sit in seats that are not broken.

Students can see the answers of peers sitting directly to their left, right, upper left, and upper right. Compute the maximum number of students that can be seated without any chance of cheating, ensuring no two students can see each other's answers.

Examples

Example 1

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

Output: 4

Teacher can place 4 students in available seats so they don't cheat on the exam.

Example 2

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

Output: 3

Place all students in available seats.

Example 3

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

Output: 10

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

Solution Approach

Enumerate Valid Row States

For each row, generate all possible seating configurations using bitmasking where no two students are adjacent and only usable seats are considered. This enumeration captures all feasible placements for dynamic programming transitions.

State Transition Between Rows

Use dynamic programming to track maximum students for each row state, ensuring that students in the current row do not conflict diagonally with students in the previous row. This ensures the cheating constraint is maintained across rows.

Combine Results Across All Rows

Iteratively update the DP table row by row, computing the total students for every compatible pair of previous and current row states. The final maximum across all last-row states yields the solution.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m * 2^n * 2^n) due to enumerating all valid row states and transitions. Space complexity is O(2^n) for storing DP values per row. Both depend heavily on n, but m is small (<=8).

What Interviewers Usually Probe

Do you recognize this as a state transition DP problem with bitmasking for seating constraints?
Can you generate all valid seating configurations per row efficiently without checking every permutation?
How would you ensure students in the current row do not see students diagonally in the previous row?

Common Pitfalls or Variants

Common pitfalls

Failing to enforce that students in the current row cannot see upper-left or upper-right neighbors in the previous row.
Not filtering out row configurations that place students in broken seats.
Incorrectly counting adjacent students in the same row which violates the no-cheating rule.

Follow-up variants

Maximize students while also minimizing empty seats between them for social distancing enforcement.
Allow only one type of diagonal visibility and compute the new maximum seating arrangement.
Extend the classroom to 3D (multiple floors) while maintaining visibility constraints per floor.

FAQ

What is the key pattern in Maximum Students Taking Exam?

The problem is a classic state transition dynamic programming with bitmasking where each row's configuration depends on the previous row to prevent cheating.

How do I represent row states efficiently?

Use bitmask integers to encode occupied seats, allowing O(1) checks for adjacency and diagonal conflicts.

Can this approach handle broken seats?

Yes, generate only valid row states where students are placed on non-broken seats, automatically excluding '#' positions.

What is the time complexity for m x n seats?

Time complexity is roughly O(m * 2^n * 2^n) since all valid row states and transitions between rows are considered.

How does GhostInterview handle cheating detection?

It uses DP with bitmasking to prevent placing students in positions where they can see each other's answers diagonally or adjacent in the same row.

terminal

Solution

Solution 1: 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 $i$th row.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

class Solution:
    def maxStudents(self, seats: List[List[str]]) -> int:
        def f(seat: List[str]) -> int:
            mask = 0
            for i, c in enumerate(seat):
                if c == '.':
                    mask |= 1 << i
            return mask

        @cache
        def dfs(seat: int, i: int) -> int:
            ans = 0
            for mask in range(1 << n):
                if (seat | mask) != seat or (mask & (mask << 1)):
                    continue
                cnt = mask.bit_count()
                if i == len(ss) - 1:
                    ans = max(ans, cnt)
                else:
                    nxt = ss[i + 1]
                    nxt &= ~(mask << 1)
                    nxt &= ~(mask >> 1)
                    ans = max(ans, cnt + dfs(nxt, i + 1))
            return ans

        n = len(seats[0])
        ss = [f(s) for s in seats]
        return dfs(ss[0], 0)

Continue Practicing

#1255 maximum score words formed by letters #996 number of squareful arrays #943 find the shortest superstring