Watch 10 video solutions for Maximum Students Taking Exam, a hard level problem involving Array, Dynamic Programming, Bit Manipulation. This walkthrough by Happy Coding has 3,343 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.lengthn == seats[i].length1 <= m <= 81 <= n <= 8Problem 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 | 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 |