Maximum Students Taking Exam: Bitmask DP on Rows

You are given an m x n matrix seats where seats[i][j] is either '.' (a good seat) or '#' (a broken seat). Students can only sit in good seats. The catch: a student can see the answers of anyone sitting directly to their left, upper-left diagonal, or upper-right diagonal. You need to find the maximum number of students you can seat so that no student can cheat off another.

This is LeetCode 1349: Maximum Students Taking Exam. It combines bitmask enumeration with row-by-row dynamic programming. If you have worked with bitmask DP before (like in subset-sum or traveling salesman variations), the structure will feel familiar. The new twist is that you are not tracking subsets of items but rather seating configurations per row, and compatibility depends on diagonal adjacency between consecutive rows.

For the grid [["#",".","#","#",".","#"],[".","#","#","#","#","."],["#",".","#","#",".","#"]], the answer is 4. You can place students at rows 0 and 2 in columns 1 and 4 each. Row 1 seats nobody because any placement there would create a cheating diagonal with rows 0 or 2.

Why bitmask DP works here

The key constraint is m up to 8 and n up to 8. With at most 8 columns, each row's seating arrangement fits in an 8-bit integer. There are at most 2^8 = 256 possible masks per row, and most of them are invalid (students on broken seats or adjacent students). The actual number of valid masks per row is much smaller.

The approach:

1. Precompute valid masks per row. For each row, enumerate all bitmasks where students sit only on good seats and no two students are in adjacent columns. A mask is valid for row i if (mask & good_seats[i]) == mask (students only on good seats) and (mask & (mask >> 1)) == 0 (no two adjacent students).

2. Define the DP. Let dp[mask] be the maximum total students seated through the current row, where mask is the seating arrangement of the current row. Process rows top to bottom. For each row, try every valid mask and pair it with every valid mask from the previous row.

3. Check compatibility between rows. Two consecutive rows with masks prev and curr are compatible if no student in the current row can see a student in the previous row diagonally. That means (curr << 1) & prev == 0 (no upper-left cheating) and (curr >> 1) & prev == 0 (no upper-right cheating).

4. Track the maximum. For each compatible pair, update dp[curr] = max(dp[curr], prev_dp[prev] + popcount(curr)).

The solution

def maxStudents(seats: list[list[str]]) -> int:
    m, n = len(seats), len(seats[0])

    # Precompute bitmask of good seats per row
    good = []
    for i in range(m):
        mask = 0
        for j in range(n):
            if seats[i][j] == '.':
                mask |= (1 << j)
        good.append(mask)

    # Enumerate all valid masks for a given row
    def valid_masks(row_good):
        masks = []
        for mask in range(1 << n):
            if mask & row_good != mask:
                continue           # student on broken seat
            if mask & (mask >> 1):
                continue           # two adjacent students
            masks.append(mask)
        return masks

    # DP: process row by row
    prev_dp = {0: 0}

    for i in range(m):
        curr_dp = {}
        for curr in valid_masks(good[i]):
            best = -1
            for prev, prev_count in prev_dp.items():
                # Check diagonal compatibility
                if (curr << 1) & prev:
                    continue       # upper-left conflict
                if (curr >> 1) & prev:
                    continue       # upper-right conflict
                best = max(best, prev_count)
            if best >= 0:
                students = bin(curr).count('1')
                curr_dp[curr] = max(curr_dp.get(curr, 0), best + students)
        # Keep empty mask if no other mask was valid
        if 0 not in curr_dp:
            curr_dp[0] = prev_dp.get(0, 0)
        prev_dp = curr_dp

    return max(prev_dp.values())

The heart of the algorithm is the nested loop: for each valid current mask, check it against every valid previous mask. The bitwise checks (curr << 1) & prev and (curr >> 1) & prev handle the diagonal constraints in O(1). The popcount of the current mask tells you how many students you are adding.

Step-by-step walkthrough

Let's trace through the example grid row by row. Watch how the DP evaluates masks and picks the best compatible pair at each step.

The critical insight in this trace is that seating 2 students in row 0 forces row 1 to be empty (all row 1 masks conflict diagonally). But then row 2 is free to seat 2 more students, giving the optimal total of 4.

Complexity analysis

Time: O(m * 4^n). For each of the m rows, you pair every valid current mask (up to 2^n) with every valid previous mask (up to 2^n). That gives 2^n * 2^n = 4^n pairs per row. With n at most 8, 4^8 = 65536 pairs per row, and m at most 8, the total is roughly 500,000 operations. In practice, the number of valid masks is much smaller than 2^n, so the algorithm runs comfortably within time limits.

Space: O(2^n). The DP dictionary stores at most 2^n entries (one per valid mask). With n at most 8, that is 256 entries.

Building blocks

Bitmask enumeration

The first building block is enumerating bitmasks that satisfy certain constraints. For each row, you iterate through all 2^n possible masks and filter by two conditions:

1. (mask & good) == mask ensures students sit only on good seats. If good = 0b010010 (columns 1 and 4 are available), then mask 0b010010 passes but 0b010100 fails because column 2 is broken.

2. (mask & (mask >> 1)) == 0 ensures no two students sit next to each other. Shifting the mask right by 1 aligns each bit with its right neighbor. If any pair of adjacent bits are both 1, the AND produces a nonzero result.

This same enumeration pattern appears in any bitmask DP where you need to filter subsets by local constraints: tiling problems, scheduling with adjacency restrictions, and coloring problems on grids.

Row-by-row DP with bitmask states

The second building block is the DP structure itself. You maintain a dictionary mapping each valid mask for the previous row to the best student count so far. For the current row, you try every valid mask, check compatibility with each previous mask, and build a new dictionary.

The compatibility check uses bit shifts:

• (curr << 1) & prev catches upper-left conflicts. Shifting curr left by 1 moves each student one column to the right. If the result overlaps with prev, a student in the current row has someone in their upper-left.
• (curr >> 1) & prev catches upper-right conflicts. Same idea, opposite direction.

Note that the "left neighbor" constraint (same row, directly to the left) is already handled by the mask & (mask >> 1) == 0 check during enumeration. You only need to check diagonals across rows.

This row-by-row DP with bitmask states is a template. Any time you have a grid where each row's configuration interacts only with the adjacent row, you can apply this pattern. The state is the previous row's bitmask. The transition checks compatibility between consecutive rows.

Edge cases

Before submitting, check these:

• All seats broken: every seat is '#'. No students can sit. Return 0.
• All seats good, 1 row: the problem reduces to finding the maximum independent set on a single row. Place students in every other column. For n columns, the answer is ceil(n / 2).
• Single column: no diagonal or left-neighbor constraints between rows. Each good seat gets a student. Return the count of '.' cells.
• 1x1 grid: if the seat is good, return 1. If broken, return 0.
• No valid placement with students: if every good seat conflicts with another, the answer can be as low as 1 (a single isolated good seat) or 0 (no good seats).
• Alternating broken and good: [[".",".",".",".","."]] on a single row gives 3 students (columns 0, 2, 4).

From understanding to recall

You have seen how bitmask DP on rows turns a combinatorial grid problem into a manageable state-space search. The two key pieces are: (1) enumerate valid masks per row using bitwise filters, and (2) check cross-row compatibility with bit shifts. With n at most 8, the entire thing runs in well under a second.

The recall cue to lock in: "each row is a bitmask, enumerate valid masks, check diagonals with shifts, DP row by row." If you can retrieve that sentence under pressure, the code writes itself.

But reading about it once is not enough. The bit manipulation details (which direction to shift for upper-left vs upper-right, how to check adjacency) are easy to mix up. Spaced repetition closes that gap. You write the solution from scratch at increasing intervals until the bitmask enumeration and compatibility checks are automatic.

The bitmask DP on rows pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Matchsticks to Square -- Backtracking with bitmask alternative for partitioning items into groups. Shows the trade-off between recursive search and bitmask DP.
• Partition to K Equal Sum Subsets -- Another problem where bitmask DP can replace backtracking. Good practice for the subset enumeration building block.
• Counting Bits -- Builds intuition for how bit manipulation recurrences work. The popcount operation used in this problem relies on the same bitwise reasoning.