# Maximum Students Taking Exam
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-students-taking-exam)
Canonical: https://scaleengineer.com/dsa/problems/maximum-students-taking-exam
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array, Matrix
**Companies:** [SAP](https://scaleengineer.com/companies/sap)
---
## Problem
Given a `m * n` matrix `seats` that represent seats distributions in a classroom. If a seat is broken, it is denoted by `'#'` character otherwise it is denoted by a `'.'` character.

Students can see the answers of those sitting next to the left, right, upper left and upper right, but he cannot see the answers of the student sitting directly in front or behind him. Return the **maximum** number of students that can take the exam together without any cheating being possible.

Students must be placed in seats in good condition.

**Example 1:**

![](https://assets.glich.co/dsa/maximum-students-taking-exam/image0.png) 

**Input:** seats = [["#",".","#","#",".","#"],
                [".","#","#","#","#","."],
                ["#",".","#","#",".","#"]]
**Output:** 4
**Explanation:** Teacher can place 4 students in available seats so they don't cheat on the exam. 

**Example 2:**

**Input:** seats = [[".","#"],
                ["#","#"],
                ["#","."],
                ["#","#"],
                [".","#"]]
**Output:** 3
**Explanation:** Place all students in available seats. 

**Example 3:**

**Input:** seats = [["#",".","**.**",".","#"],
                ["**.**","#","**.**","#","**.**"],
                ["**.**",".","#",".","**.**"],
                ["**.**","#","**.**","#","**.**"],
                ["#",".","**.**",".","#"]]
**Output:** 10
**Explanation:** Place students in available seats in column 1, 3 and 5.

**Constraints:**

* `seats` contains only characters `'.' and` `'#'.`
* `m == seats.length`
* `n == seats[i].length`
* `1 <= m <= 8`
* `1 <= n <= 8`

# Approaches
## Brute-force Backtracking
A naive approach is to try every possible way of placing students. We can iterate through each available seat and decide whether to place a student there or not. This is equivalent to generating all subsets of available seats. For each subset, we check if it's a valid arrangement (i.e., no two students can cheat). We then keep track of the size of the largest valid subset found. This can be implemented using recursion or backtracking.
**Time:** O(2^k * k^2), where k is the number of available seats (k <= m*n). For each of the 2^k subsets of seats, we perform a check for conflicts which can take up to O(k^2) time. This is too slow for the given constraints. · **Space:** O(k), where k is the number of available seats. This space is used for the recursion stack.
**Pros:** Simple to understand and implement.; Guaranteed to find the correct answer by exploring all possibilities.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
This method explores the entire search space of student placements. We can represent the state by the index of the seat we are considering and the configuration of students placed so far. For each seat, we branch into two possibilities: placing a student or not. We prune branches where a placement creates a conflict. While simple to understand, this approach is computationally expensive because the number of subsets grows exponentially with the number of available seats.
### Algorithm
- Define a recursive function, for example `backtrack(index, placements)`, where `index` is the index of the current available seat being considered, and `placements` is the set of seats where students are already placed.
- Get a list of all available seats (where `seats[r][c] == '.'`).
- The recursion works as follows:
  - **Base Case:** If `index` equals the total number of available seats, it means we have considered all seats. The number of students is the size of `placements`. We update our global maximum answer.
  - **Recursive Step:** For the seat at `available_seats[index]`, we have two choices:
    1. **Place a student:** Check if placing a student at this seat conflicts with any student in the `placements` set. A conflict occurs if the new seat is adjacent (left, right, upper-left, upper-right, lower-left, lower-right) to any existing seat in `placements`. If there is no conflict, we add the seat to `placements` and recurse: `backtrack(index + 1, new_placements)`.
    2. **Do not place a student:** We simply move to the next seat without changing the placements: `backtrack(index + 1, placements)`.
- The initial call would be `backtrack(0, empty_set)`.

## Dynamic Programming with Bitmasking
This problem has optimal substructure and overlapping subproblems, making it suitable for dynamic programming. We can process the grid row by row. The decision of placing students in the current row depends only on the placement in the immediately preceding row. We can use bitmasking to represent the state of each row, where each bit in an integer corresponds to a column in the grid.
**Time:** O(m * 4^n), where m is the number of rows and n is the number of columns. For each of the `m` rows, we iterate through `2^n` possible masks for the current row and `2^n` masks for the previous row. · **Space:** O(2^n), where n is the number of columns. We only need to store the DP results for the previous row to compute the current one.
**Pros:** Much more efficient than brute-force.; A standard technique for solving problems on grid-like structures with local dependencies.
**Cons:** The time complexity is exponential in the number of columns `n`.; It is less efficient than the bipartite matching approach for the given constraints.
### Explanation
We can define a DP state `dp[i][mask]` representing the maximum students in the first `i` rows, with the `i`-th row having a student arrangement given by `mask`. To compute `dp[i][mask]`, we must first ensure `mask` is a valid arrangement for row `i` itself (no students on broken seats, no adjacent students). Then, we iterate through all possible valid masks for the previous row (`prev_mask`) and check if they are compatible with `current_mask`. If they are, we can transition from that state. The final answer is the maximum value in the last row of our DP table.

Here is a Java implementation with space optimization:
```java
class Solution {
    public int maxStudents(char[][] seats) {
        int m = seats.length;
        int n = seats[0].length;
        
        int[] brokenSeats = new int[m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (seats[i][j] == '#') {
                    brokenSeats[i] |= (1 << j);
                }
            }
        }

        int[] dp = new int[1 << n];
        
        for (int i = 0; i < m; i++) {
            int[] next_dp = new int[1 << n];
            for (int currentMask = 0; currentMask < (1 << n); currentMask++) {
                if ((currentMask & brokenSeats[i]) == 0 && (currentMask & (currentMask >> 1)) == 0) {
                    int studentsCount = Integer.bitCount(currentMask);
                    int maxPrevStudents = 0;
                    for (int prevMask = 0; prevMask < (1 << n); prevMask++) {
                        if ((currentMask & (prevMask >> 1)) == 0 && (currentMask & (prevMask << 1)) == 0) {
                            maxPrevStudents = Math.max(maxPrevStudents, dp[prevMask]);
                        }
                    }
                    next_dp[currentMask] = maxPrevStudents + studentsCount;
                }
            }
            dp = next_dp;
        }

        int maxStudents = 0;
        for (int count : dp) {
            maxStudents = Math.max(maxStudents, count);
        }
        return maxStudents;
    }
}
```
### Algorithm
- The state of student placements in a row `r` only depends on the placements in the previous row `r-1`. This allows for a row-by-row dynamic programming approach.
- We use a bitmask of length `n` to represent the student arrangement in a single row. A `1` at bit `j` means a student is at column `j`, and a `0` means no student.
- Let `dp[r][mask]` be the maximum number of students that can be placed in rows `0` to `r`, with row `r` having the arrangement `mask`.
- The state transition is: `dp[r][mask] = Integer.bitCount(mask) + max(dp[r-1][prev_mask])` for all `prev_mask` that are compatible with `mask`.
- A `mask` for row `r` is valid if:
  1. It doesn't place students on broken seats (`#`).
  2. No two students are adjacent in the same row: `(mask & (mask >> 1)) == 0`.
- A `prev_mask` for row `r-1` is compatible with `mask` for row `r` if:
  1. No upper-left conflict: `(mask & (prev_mask >> 1)) == 0`.
  2. No upper-right conflict: `(mask & (prev_mask << 1)) == 0`.
- To optimize space, we can use only two arrays, one for the current row's DP values and one for the previous row's, leading to `O(2^n)` space.

## Bipartite Matching (Maximum Independent Set)
A more efficient approach involves reframing the problem in terms of graph theory. We can model the classroom seats as a graph where an edge exists between two seats if students placed there can cheat off each other. The goal is to find the maximum number of vertices with no edges between them, which is the Maximum Independent Set (MIS) problem. For general graphs, MIS is NP-hard. However, the conflict graph in this problem has a special structure: it's bipartite. This allows us to solve the problem efficiently.
**Time:** O(V * E) using a simple augmenting path algorithm, where V is the number of seats and E is the number of conflicts. In the worst case, this is O((m*n)^2). For the given constraints, this is significantly faster than the DP approach. · **Space:** O(m*n), to store the graph and data structures for the matching algorithm.
**Pros:** The most efficient approach with a polynomial time complexity.; Scales better than the DP approach as `n` increases.
**Cons:** More complex to understand and implement, requiring knowledge of graph theory (bipartite graphs, maximum matching).; The implementation can be more verbose than the DP approach.
### Explanation
By partitioning the seats based on column parity (even vs. odd columns), we can construct a bipartite graph. All cheating constraints apply between a seat in an even column and a seat in an odd column. Once we have this bipartite graph, we can find the size of the maximum independent set. By Konig's theorem, this size is equal to the total number of vertices (available seats) minus the size of the maximum matching in the graph. We can find the maximum matching using a standard algorithm, such as finding augmenting paths via Depth First Search.

Here is a Java implementation:
```java
import java.util.*;

class Solution {
    private List<Integer>[] adj;
    private int[] match;
    private boolean[] visited;

    public int maxStudents(char[][] seats) {
        int m = seats.length;
        int n = seats[0].length;
        
        List<int[]> evenColSeats = new ArrayList<>();
        List<int[]> oddColSeats = new ArrayList<>();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (seats[i][j] == '.') {
                    if (j % 2 == 0) {
                        evenColSeats.add(new int[]{i, j});
                    } else {
                        oddColSeats.add(new int[]{i, j});
                    }
                }
            }
        }

        int uSize = evenColSeats.size();
        int vSize = oddColSeats.size();
        adj = new ArrayList[uSize];
        for(int i=0; i<uSize; i++) adj[i] = new ArrayList<>();

        for (int i = 0; i < uSize; i++) {
            int r1 = evenColSeats.get(i)[0];
            int c1 = evenColSeats.get(i)[1];
            for (int j = 0; j < vSize; j++) {
                int r2 = oddColSeats.get(j)[0];
                int c2 = oddColSeats.get(j)[1];
                if (Math.abs(r1 - r2) <= 1 && Math.abs(c1 - c2) == 1) {
                    adj[i].add(j);
                }
            }
        }

        match = new int[vSize];
        Arrays.fill(match, -1);
        int matchingSize = 0;
        
        for (int i = 0; i < uSize; i++) {
            visited = new boolean[vSize];
            if (dfs(i)) {
                matchingSize++;
            }
        }
        
        return (uSize + vSize) - matchingSize;
    }

    private boolean dfs(int u) {
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                if (match[v] < 0 || dfs(match[v])) {
                    match[v] = u;
                    return true;
                }
            }
        }
        return false;
    }
}
```
### Algorithm
- **Model as a Graph Problem:** The problem is equivalent to finding the Maximum Independent Set (MIS) on a 'conflict graph'. The vertices are the available seats, and an edge connects two seats if placing students in both is forbidden.
- **Bipartite Graph:** Observe the conflict rules. A student at `(r, c)` conflicts with neighbors at `(r, c±1)`, `(r±1, c±1)`. If we color the columns alternately (like a checkerboard), a seat in an even column only conflicts with seats in odd columns. This means the conflict graph is bipartite.
- **Konig's Theorem:** For any bipartite graph, the size of a maximum independent set is equal to the total number of vertices minus the size of a maximum matching (`alpha(G) = |V| - nu(G)`).
- **Algorithm Steps:**
  1. Count the total number of available seats (`.`), let this be `total_seats`.
  2. Construct a bipartite graph: Partition available seats into `U` (even columns) and `V` (odd columns).
  3. Add an edge between a seat `u` in `U` and `v` in `V` if they conflict.
  4. Find the size of the maximum matching in this graph using an algorithm like Hopcroft-Karp or a simpler augmenting path search with DFS/BFS.
  5. The result is `total_seats - max_matching_size`.

# Solutions
### Java

```java
class Solution { private Integer [][] f ; private int n ; private int [] ss ; public int maxStudents ( char [][] seats ) { int m = seats . length ; n = seats [ 0 ]. length ; ss = new int [ m ]; f = new Integer [ 1 << n ][ m ]; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { if ( seats [ i ][ j ] == '.' ) { ss [ i ] |= 1 << j ; } } } return dfs ( ss [ 0 ], 0 ); } private int dfs ( int seat , int i ) { if ( f [ seat ][ i ] != null ) { return f [ seat ][ i ]; } int ans = 0 ; for ( int mask = 0 ; mask < 1 << n ; ++ mask ) { if (( seat | mask ) != seat || ( mask & ( mask << 1 )) != 0 ) { continue ; } int cnt = Integer . bitCount ( mask ); if ( i == ss . length - 1 ) { ans = Math . max ( ans , cnt ); } else { int nxt = ss [ i + 1 ]; nxt &= ~( mask << 1 ); nxt &= ~( mask >> 1 ); ans = Math . max ( ans , cnt + dfs ( nxt , i + 1 )); } } return f [ seat ][ i ] = ans ; } }
```

### CPP

```cpp
class Solution { public: int maxStudents ( vector < vector < char >>& seats ) { int m = seats . size (); int n = seats [ 0 ]. size (); vector < int > ss ( m ); vector < vector < int >> f ( 1 << n , vector < int > ( m , - 1 )); for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { if ( seats [ i ][ j ] == '.' ) { ss [ i ] |= 1 << j ; } } } function < int ( int , int ) > dfs = [ & ]( int seat , int i ) -> int { if ( f [ seat ][ i ] != - 1 ) { return f [ seat ][ i ]; } int ans = 0 ; for ( int mask = 0 ; mask < 1 << n ; ++ mask ) { if (( seat | mask ) != seat || ( mask & ( mask << 1 )) != 0 ) { continue ; } int cnt = __builtin_popcount ( mask ); if ( i == m - 1 ) { ans = max ( ans , cnt ); } else { int nxt = ss [ i + 1 ]; nxt &= ~ ( mask >> 1 ); nxt &= ~ ( mask << 1 ); ans = max ( ans , cnt + dfs ( nxt , i + 1 )); } } return f [ seat ][ i ] = ans ; }; return dfs ( ss [ 0 ], 0 ); } };
```

### Python

```python
class Solution : def maxStudents ( self , seats : List [ List [ str ]]) -> int : def f ( seat : List [ str ]) -> int : mask = 0 for i , c in enumerate ( seat ): if c == '.' : mask |= 1 << i return mask @ cache def dfs ( seat : int , i : int ) -> int : ans = 0 for mask in range ( 1 << n ): if ( seat | mask ) != seat or ( mask & ( mask << 1 )): continue cnt = mask . bit_count () if i == len ( ss ) - 1 : ans = max ( ans , cnt ) else : nxt = ss [ i + 1 ] nxt &= ~ ( mask << 1 ) nxt &= ~ ( mask >> 1 ) ans = max ( ans , cnt + dfs ( nxt , i + 1 )) return ans n = len ( seats [ 0 ]) ss = [ f ( s ) for s in seats ] return dfs ( ss [ 0 ], 0 )
```