Problem Description

You are given a 2D array seats representing a classroom of students about to take an exam. Each element of seats is either '.' (an available seat) or '#' (a broken seat). The classroom has m rows and n columns.

A student can sit in a seat if it is available. However, to prevent cheating, no two students can sit in seats that are adjacent horizontally or diagonally (i.e., a student cannot sit directly to the left, right, upper-left, or upper-right of another student).

Your task is to determine the maximum number of students that can take the exam without violating the above constraints. Each seat can be used at most once, and you cannot reuse elements.

Thought Process

At first glance, the problem appears to be a variant of the classic "maximum independent set" problem on a grid, with additional adjacency constraints. A brute-force approach would be to try every possible combination of students sitting in available seats and check if the constraints are satisfied. However, the number of combinations grows exponentially with the number of seats, making brute-force infeasible for larger grids.

To solve this efficiently, we need a way to represent the state of each row and quickly check for conflicts. Since each seat can be either occupied or not, we can represent each row as a bitmask, where each bit indicates whether a student sits in a particular seat. We can then use dynamic programming (DP) to build up solutions row by row, only considering valid seatings and keeping track of the best possible arrangement so far.

The key insight is to use bitmasking to efficiently encode seat assignments and to use DP to avoid recalculating overlapping subproblems.

Solution Approach

Let's break down the steps to solve the problem efficiently:

1. Bitmask Representation: For each row, generate a bitmask where 1 means a student sits in that seat, and 0 means the seat is empty or broken.
2. Valid Row States: For each row, enumerate all possible seatings (bitmasks) that do not put students in broken seats and do not have students sitting next to each other horizontally.
3. DP Table: Use a DP table where dp[row][mask] represents the maximum number of students for the first row rows, ending with seating configuration mask on the current row.
4. Transition: For each valid configuration in the current row, check all valid configurations from the previous row. Only transfer if no two students are diagonally adjacent (i.e., left-up or right-up).
5. Counting Students: For each valid mask, count the number of students (number of set bits).
6. Result: The answer is the maximum value in the last row of the DP table.

This approach leverages bitmasking for fast adjacency checks and DP for optimal substructure, making it much more efficient than brute-force.

Example Walkthrough

Suppose seats = [[".", "#", ".", ".", "#"], [".", ".", "#", ".", "."], ["#", ".", "#", ".", "#"]].

• Row 0: Possible valid seatings are those where students are not adjacent and not on broken seats. For example, 10100 (student in seat 0 and 2) is valid.
• Row 1: For each valid mask in row 1, check that it does not have students diagonally adjacent to those in the previous row. For instance, if row 0 has 10100, row 1 cannot have a student in seat 1 or 3.
• DP Update: For each valid pair of masks (prev row, curr row), update the DP table with the sum of students.
• Continue: Repeat for each row, always checking both horizontal and diagonal adjacency.
• Final Answer: After processing all rows, the maximum value in the last row's DP entries is the answer.

For this example, the optimal arrangement allows 4 students without violating the constraints.

Code Implementation

class Solution:
    def maxStudents(self, seats):
        m, n = len(seats), len(seats[0])
        valid = []
        for row in seats:
            mask = 0
            for j, c in enumerate(row):
                if c == '.':
                    mask |= (1 << j)
            valid.append(mask)

        from collections import defaultdict
        dp = {0: 0}
        for i in range(m):
            ndp = defaultdict(int)
            for curr in range(1 << n):
                if (curr & ~valid[i]) != 0: continue
                if (curr & (curr << 1)) != 0: continue
                for prev in dp:
                    if (curr & (prev << 1)) != 0: continue
                    if (curr & (prev >> 1)) != 0: continue
                    ndp[curr] = max(ndp[curr], dp[prev] + bin(curr).count('1'))
            dp = ndp
        return max(dp.values()) if dp else 0
      

class Solution {
public:
    int maxStudents(vector<vector<char>>& seats) {
        int m = seats.size(), n = seats[0].size();
        vector<int> valid(m, 0);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (seats[i][j] == '.') valid[i] |= (1 << j);
            }
        }
        unordered_map<int, int> dp;
        dp[0] = 0;
        for (int i = 0; i < m; ++i) {
            unordered_map<int, int> ndp;
            for (int curr = 0; curr < (1 << n); ++curr) {
                if ((curr & ~valid[i]) != 0) continue;
                if ((curr & (curr << 1)) != 0) continue;
                for (auto& p : dp) {
                    int prev = p.first;
                    if ((curr & (prev << 1)) != 0) continue;
                    if ((curr & (prev >> 1)) != 0) continue;
                    int cnt = __builtin_popcount(curr);
                    ndp[curr] = max(ndp[curr], dp[prev] + cnt);
                }
            }
            dp = ndp;
        }
        int res = 0;
        for (auto& p : dp) res = max(res, p.second);
        return res;
    }
};
      

class Solution {
    public int maxStudents(char[][] seats) {
        int m = seats.length, n = seats[0].length;
        int[] valid = new int[m];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (seats[i][j] == '.') valid[i] |= (1 << j);
            }
        }
        Map<Integer, Integer> dp = new HashMap<>();
        dp.put(0, 0);
        for (int i = 0; i < m; ++i) {
            Map<Integer, Integer> ndp = new HashMap<>();
            for (int curr = 0; curr < (1 << n); ++curr) {
                if ((curr & ~valid[i]) != 0) continue;
                if ((curr & (curr << 1)) != 0) continue;
                for (int prev : dp.keySet()) {
                    if ((curr & (prev << 1)) != 0) continue;
                    if ((curr & (prev >> 1)) != 0) continue;
                    int cnt = Integer.bitCount(curr);
                    ndp.put(curr, Math.max(ndp.getOrDefault(curr, 0), dp.get(prev) + cnt));
                }
            }
            dp = ndp;
        }
        int res = 0;
        for (int v : dp.values()) res = Math.max(res, v);
        return res;
    }
}
      

var maxStudents = function(seats) {
    let m = seats.length, n = seats[0].length;
    let valid = new Array(m).fill(0);
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (seats[i][j] === '.') valid[i] |= (1 << j);
        }
    }
    let dp = new Map();
    dp.set(0, 0);
    for (let i = 0; i < m; ++i) {
        let ndp = new Map();
        for (let curr = 0; curr < (1 << n); ++curr) {
            if ((curr & ~valid[i]) !== 0) continue;
            if ((curr & (curr << 1)) !== 0) continue;
            for (let [prev, val] of dp.entries()) {
                if ((curr & (prev << 1)) !== 0) continue;
                if ((curr & (prev >> 1)) !== 0) continue;
                let cnt = curr.toString(2).split('1').length - 1;
                ndp.set(curr, Math.max(ndp.get(curr) || 0, val + cnt));
            }
        }
        dp = ndp;
    }
    let res = 0;
    for (let v of dp.values()) res = Math.max(res, v);
    return res;
};
      

Time and Space Complexity

Brute-force: The brute-force approach would try every subset of available seats, leading to O(2^{m \times n}) time, which is not feasible for even moderate grid sizes.

Optimized DP Approach:

• For each row, there are at most 2^n possible seatings (bitmasks).
• For each mask in a row, we check all masks from the previous row, so per row the work is O(2^n \times 2^n).
• Total time complexity: O(m \times 2^n \times 2^n) = O(m \times 4^n).
• Space complexity: At each step, we store at most 2^n DP states, so O(2^n) space.

This is efficient for n \leq 8 (as per Leetcode constraints), making the approach practical.

Summary

The problem challenges us to maximize the number of students taking an exam in a classroom with adjacency constraints. By representing seat arrangements with bitmasks and using dynamic programming to build up solutions row by row, we efficiently avoid redundant calculations and ensure all constraints are respected. The key insight is leveraging bit manipulation for fast state checks and DP for optimal substructure, resulting in an elegant and performant solution.