1471. Maximum Students Taking Exam
My accepted Python solution to LeetCode problem 1471, Maximum Students Taking Exam, running in 8ms.
- Difficulty: Hard
- Python
- Runtime 8ms
- Memory 17.6MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 8ms, memory 17.6MB, accepted 2025-12-29.
class Solution:
def maxStudents(self, seats: List[List[str]]) -> int:
m, n = len(seats), len(seats[0])
# Create valid seat masks for each row
valid = []
for i in range(m):
mask = 0
for j in range(n):
if seats[i][j] == '.':
mask |= (1 << j)
valid.append(mask)
# dp[mask] = max students for current row with state mask
prev_dp = {0: 0}
for row in range(m):
curr_dp = {}
row_valid = valid[row]
# Generate all valid arrangements for this row
mask = row_valid
while True:
# Check no adjacent students in same row
if not (mask & (mask >> 1)):
for prev_mask, prev_count in prev_dp.items():
# Check no cheating from previous row
if not ((mask & (prev_mask >> 1)) or (mask & (prev_mask << 1))):
count = prev_count + bin(mask).count('1')
if mask not in curr_dp or curr_dp[mask] < count:
curr_dp[mask] = count
if mask == 0:
break
mask = (mask - 1) & row_valid
prev_dp = curr_dp if curr_dp else {0: 0}
return max(prev_dp.values()) if prev_dp else 0