Python 1349.py
class Solution:
def maxStudents(self, seats: List[List[str]]) -> int:
height = len(seats)
width = len(seats[0])
# convert seat map to bitmasks
allowed = []
for h in range(height):
mask = 0
for s in seats[h]:
mask <<= 1
mask += 1 if s == "." else 0
allowed.append(mask)
# figure out which seat combinations are allowed behind each combination
combinations = 1 << width
compatible = [ [] for _ in range(combinations) ]
for upper in range(combinations):
# only relevant
okay = False
for a in allowed:
if upper == 0 or ((upper & a) == upper):
okay = True
break
if not okay:
continue
for lower in range(combinations):
# noone must sit to the left or right
if lower & (lower >> 1):
continue
# noone must sit diagonally in front
if ((upper << 1) | (upper >> 1)) & lower:
continue
# only relevant
for a in allowed:
if (lower & a) == lower:
compatible[upper].append(lower)
break
@cache
def deeper(row, upper):
if row == height:
return 0
best = 0
free = allowed[row]
for c in compatible[upper]:
if (c | free) == free:
best = max(best, deeper(row + 1, c) + c.bit_count())
return best
return deeper(0, 0)
Difficulty
and has an acceptance rate of about 52% (30k+ submissions).
Typical patterns to solve this problem:
- Array
- Bit Manipulation
- Bitmask
- Dynamic Programming
- Matrix
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The implementation solves the “maximum students that can take an exam” problem by modeling each row of seats as a bitmask and then performing a depth-first search with memoization over the rows. The core idea is to enumerate all feasible seat configurations for a single row, pre-compute which configurations can sit behind each other without violating the adjacency and diagonal constraints, and finally use a cached recursive function to choose the optimal combination across all rows.
Bitmask representation of the classroom
The first phase translates the 2-D seat map into a list of integer masks, where each bit indicates whether the corresponding position is usable (.) or blocked (#).
height = len(seats)
width = len(seats[0])
allowed = []
for h in range(height):
mask = 0
for s in seats[h]:
mask <<= 1
mask += 1 if s == "." else 0
allowed.append(mask)
Each entry in allowed contains a mask whose 1 bits correspond to seats that are physically present. This compact representation enables fast bitwise operations for later compatibility checks.
Enumerating row configurations
A row can contain at most width seats, so there are 2**width possible occupancy patterns. The code iterates over every pattern (upper) and discards those that cannot be placed on any actual row of the classroom. The check ((upper & a) == upper) ensures that every occupied seat in the pattern aligns with a usable seat in at least one row.
combinations = 1 << width
compatible = [ [] for _ in range(combinations) ]
for upper in range(combinations):
okay = False
for a in allowed:
if upper == 0 or ((upper & a) == upper):
okay = True
break
if not okay:
continue
The okay flag filters out patterns that would require a seat that does not exist, effectively pruning the search space early.
Compatibility between consecutive rows
For each viable upper pattern, the algorithm examines every possible lower pattern and applies two constraints:
- No two occupied seats may be adjacent in the same row. This is detected by
lower & (lower >> 1). - No occupied seat may sit diagonally in front of another. The expression
((upper << 1) | (upper >> 1)) & lowercaptures the left- and right-shifted positions of the upper row and checks for overlap with the lower row.
If a lower pattern satisfies both constraints, the code then verifies that the pattern fits within the physical layout of at least one row ((lower & a) == lower). When all checks pass, lower is recorded as a compatible successor of upper.
for lower in range(combinations):
if lower & (lower >> 1):
continue
if ((upper << 1) | (upper >> 1)) & lower:
continue
for a in allowed:
if (lower & a) == lower:
compatible[upper].append(lower)
break
The compatible list thus maps each upper configuration to all lower configurations that can legally follow it, eliminating the need to recompute constraints during the recursive search.
Recursive search with memoization
The heart of the solution is a depth-first search that proceeds row by row, selecting a compatible configuration for the current row and recursing to the next. The @cache decorator memoizes results for each (row, upper) pair, guaranteeing that each subproblem is solved only once.
@cache
def deeper(row, upper):
if row == height:
return 0
best = 0
free = allowed[row]
for c in compatible[upper]:
if (c | free) == free:
best = max(best, deeper(row + 1, c) + c.bit_count())
return best
The termination condition returns zero when all rows have been processed. For the current row, free holds the mask of usable seats. The loop iterates over all c that are compatible with the previous row’s configuration (upper). The test (c | free) == free ensures that the candidate configuration does not occupy any blocked seat in the current row. The expression c.bit_count() yields the number of students seated in this configuration, which is added to the best result obtained from deeper rows.
The final answer is obtained by invoking the recursive function with the first row and an empty upper configuration:
return deeper(0, 0)
Edge-case handling
The algorithm gracefully handles several edge conditions:
- An empty classroom (zero rows) is covered by the base case
if row == height: return 0, returning zero students. - Rows that contain no usable seats produce a mask of zero; the compatibility logic treats the all-zero pattern as universally compatible, allowing the recursion to skip those rows without penalty.
- A single column (
width == 1) simplifies the adjacency check becauselower & (lower >> 1)always yields zero, and diagonal checks reduce to simple shifts, still correctly preventing vertical adjacency. - The presence of completely blocked rows does not affect the pre-computed
compatiblestructure because the compatibility loop only adds successors that fit within at least one allowed mask.
Performance optimizations
The solution incorporates several techniques that reduce computational overhead:
- Bitmask encoding compresses the seat layout into integers, enabling constant-time logical operations for adjacency and diagonal checks.
- Early pruning of impossible patterns via the
okayflag prevents the construction of compatibility lists for configurations that could never be placed, shrinking the size ofcompatible. - Pre-computation of compatibility moves the expensive pairwise checks out of the recursive phase, so the depth-first search only iterates over already validated successors.
- Memoization with
@cacheeliminates redundant recomputation of subproblems, ensuring that each(row, upper)state is evaluated once regardless of how many paths lead to it. - Bit counting using the built-in
bit_count()method provides a fast way to tally occupied seats without iterating over individual bits.
Collectively, these strategies keep the algorithm efficient even when the classroom width approaches the practical limit for exhaustive enumeration (typically up to 8 or 10 columns). The combination of bitwise manipulation, pre-filtered candidate sets, and cached recursion yields a solution that scales well within the constraints of the problem.
ELI5 - Simplified Explanation
Imagine a big classroom filled with desks. Some desks are broken and cannot be used, while others are perfectly fine. Students want to sit down, but they have special rules. They cannot sit right next to someone, and they cannot sit diagonally in front of someone either. This code helps figure out the absolute maximum number of students who can fit into the classroom at the same time without breaking any of those rules.
First, the code looks at every single row in the classroom to see which spots are actually available. It turns these rows into a special computer code made of bits, which acts like a checklist for where people are allowed to sit.
Next, it carefully checks which rows can go in front of other rows. It looks at every possible pattern of chairs in one row and compares it to a pattern behind it. If nobody is sitting too close to a neighbor or looking over a shoulder diagonally, then that pairing is allowed. It creates a list of these friendly combinations so it does not have to do the math over and over again.
Finally, it starts a game of choosing spots row by row. It looks at the first row, picks a valid pattern, and then moves to the next row to see what fits best based on the first choice. Because there are so many ways to arrange chairs, it uses a trick to remember the best results it has already found. By looking at all the options from the front of the room to the back, it keeps track of the biggest number of students that can fit safely.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | ||||||||
|---|---|---|---|---|---|---|---|---|
| author | solutions | |||||||
| www | AlgoMonster | C++ | Java | Python | TS | |||
| WalkCCC | C++ | Java | Python | |||||
| leetcode.ca | C++ | Java | Go | Python | TS | |||
| Progiez | C++ | Java | Python | |||||
| github | black-shadows | C++ | ||||||
| charles-wangkai | Java | |||||||
| everthis | JS | |||||||
| fsq | C++ | |||||||
| JoshCrozier | JS | |||||||
| keineahnung2345 | C++ | |||||||
| lzl124631x | C++ | |||||||
| suxrobGM | C# | |||||||
| wisdompeak | C++ | |||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||
| WalkCCC | C++, Python, Java | |||||||
| leetcode.ca | C++, Go, Java, Python, TypeScript | |||||||
| Progiez | C++, Java, Python | |||||||
| black-shadows | C++, C++ | |||||||
| charles-wangkai | Java | |||||||
| everthis | JavaScript | |||||||
| fsq | C++ | |||||||
| JoshCrozier | JavaScript | |||||||
| keineahnung2345 | C++ | |||||||
| lzl124631x | C++ | |||||||
| suxrobGM | C# | |||||||
| wisdompeak | C++ |
Videos
Solved On The Same Day
- problem 2861: Maximum Number of Alloys
- problem 1383: Maximum Performance of a Team
- problem 1851: Minimum Interval to Include Each Query
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality