Maximum Students Taking Exam — Problem & Solution
Maximum Students Taking Exam solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Maximum Students Taking Exam is a hard coding problem on dynamic programming, matrix and bit manipulation, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Dynamic Programming, Matrix, Bit Manipulation, Bitmask
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A classroom is described by seats, an m x n grid given as m strings of length n: '.' is a usable seat and '#' is a broken one.
A student can see the answer sheets of students sitting directly to their left, right, upper left and upper right, but not of the students directly in front of or behind them. Seat students only in usable seats so that no student can see another student's answers.
Return the maximum number of students that can take the exam together.
Example 1
Input: seats = [".#.#.","....."]
Output: 6
Explanation: Columns 0, 2 and 4 in both rows. The back row's diagonals all point at broken seats, and same-column seats do not see each other.
Example 2
Input: seats = ["..",".."]
Output: 2
Explanation: Both seats of one column — any other pair is side by side or diagonal.
Example 3
Input: seats = ["#"]
Output: 0
Constraints
seats.length == mseats[i].length == n1 <= m, n <= 8seats[i][j] is '.' or '#'
Hints for Maximum Students Taking Exam
Hint 1
Process the room row by row. Which seats in one row can be filled together, and how does a row constrain the next one?
Hint 2
Encode a row's occupied seats as a bitmask. Within a row no two set bits may be adjacent; across consecutive rows, the lower row's mask may not overlap the upper row's mask shifted left or right by one.
Hint 3
Let
dp[row][mask]be the most students in rows0..rowwithmaskoccupied inrow. With at most 8 columns there are few valid masks per row, so trying every pair of consecutive masks is cheap.
How to solve Maximum Students Taking Exam
Conflicts only connect a row with itself and with the row directly above, so a DP over rows whose state is the occupancy bitmask of the current row captures everything that matters.
Approach
- For each row compute
good, the mask of usable seats. - A row mask is valid if it is a subset of
goodand has no two adjacent bits (mask AND (mask << 1) == 0). - Start from the empty row (
dp = {0: 0}). For each row and each valid mask, take the best previous maskpwithmask AND (p << 1) == 0andmask AND (p >> 1) == 0, and store that value pluspopcount(mask). - Return the largest value after the last row.
Why it works
Every forbidden pair is either two neighbours in one row (ruled out by the adjacency test) or a student and someone in the row above at a diagonal (ruled out by the two shifted tests); pairs two or more rows apart never conflict. So an arrangement is valid exactly when each row mask is valid and each consecutive pair is compatible, and the DP maximises over all such sequences.
Complexity
- Time —
O(m · F²), F ≤ 55 valid masks per row - Space —
O(2^n)
Pitfalls
- Students directly in front or behind do not conflict — only the diagonals of the row above (and below, which is the same relation).
- Check broken seats with the
goodmask, not just adjacency. - Keep only reachable previous masks to avoid scanning all 2^n × 2^n pairs.
Reference solution
Python
from typing import List
def maxStudents(seats: List[str]) -> int:
n = len(seats[0])
prev = {0: 0}
for row in seats:
good = 0
for c in range(n):
if row[c] == ".":
good |= 1 << c
cur = {}
for mask in range(1 << n):
if (mask & ~good) or (mask & (mask << 1)):
continue
best = -1
for p, v in prev.items():
if (mask & (p << 1)) or (mask & (p >> 1)):
continue
if v > best:
best = v
if best >= 0:
cur[mask] = best + bin(mask).count("1")
prev = cur
return max(prev.values())Java
public static int maxStudents(String[] seats) {
int n = seats[0].length(), full = 1 << n;
int[] prevMasks = new int[full], prevVals = new int[full];
int[] curMasks = new int[full], curVals = new int[full];
int pl = 1;
prevMasks[0] = 0;
prevVals[0] = 0;
for (String row : seats) {
int good = 0;
for (int c = 0; c < n; c++) if (row.charAt(c) == '.') good |= 1 << c;
int cl = 0;
for (int mask = 0; mask < full; mask++) {
if ((mask & ~good) != 0 || (mask & (mask << 1)) != 0) continue;
int best = -1;
for (int t = 0; t < pl; t++) {
int p = prevMasks[t];
if ((mask & (p << 1)) != 0 || (mask & (p >> 1)) != 0) continue;
best = Math.max(best, prevVals[t]);
}
if (best < 0) continue;
curMasks[cl] = mask;
curVals[cl] = best + Integer.bitCount(mask);
cl++;
}
int[] tmp = prevMasks; prevMasks = curMasks; curMasks = tmp;
tmp = prevVals; prevVals = curVals; curVals = tmp;
pl = cl;
}
int ans = 0;
for (int t = 0; t < pl; t++) ans = Math.max(ans, prevVals[t]);
return ans;
}C++
int maxStudents(vector<string>& seats) {
int n = seats[0].size(), full = 1 << n;
vector<pair<int, int>> prev(1, make_pair(0, 0)), cur;
for (const string& row : seats) {
int good = 0;
for (int c = 0; c < n; c++) if (row[c] == '.') good |= 1 << c;
cur.clear();
for (int mask = 0; mask < full; mask++) {
if ((mask & ~good) || (mask & (mask << 1))) continue;
int best = -1;
for (auto& pv : prev) {
if ((mask & (pv.first << 1)) || (mask & (pv.first >> 1))) continue;
best = max(best, pv.second);
}
if (best < 0) continue;
cur.push_back(make_pair(mask, best + __builtin_popcount(mask)));
}
swap(prev, cur);
}
int ans = 0;
for (auto& pv : prev) ans = max(ans, pv.second);
return ans;
}JavaScript
var maxStudents = function(seats) {
var n = seats[0].length, full = 1 << n;
var prevMasks = [0], prevVals = [0];
for (var r = 0; r < seats.length; r++) {
var good = 0;
for (var c = 0; c < n; c++) if (seats[r][c] === ".") good |= 1 << c;
var curMasks = [], curVals = [];
for (var mask = 0; mask < full; mask++) {
if ((mask & ~good) || (mask & (mask << 1))) continue;
var best = -1;
for (var t = 0; t < prevMasks.length; t++) {
var p = prevMasks[t];
if ((mask & (p << 1)) || (mask & (p >> 1))) continue;
if (prevVals[t] > best) best = prevVals[t];
}
if (best < 0) continue;
var cnt = 0;
for (var x = mask; x; x >>= 1) cnt += x & 1;
curMasks.push(mask);
curVals.push(best + cnt);
}
prevMasks = curMasks;
prevVals = curVals;
}
var ans = 0;
for (var k = 0; k < prevVals.length; k++) if (prevVals[k] > ans) ans = prevVals[k];
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming · Matrix and Grid Traversal