Hard

Maximum Students Taking Exam

LAB

Seats are encoded with . for usable and # for broken. Return the maximum students seated without adjacent cheating horizontally or diagonally forward.

EXAMPLES

Example 1

Input
{
  "seats": [
    "#..#",
    "....",
    ".##.",
    "#..#"
  ]
}

Output
4

FUNCTION SHAPE

seats: stringArray→int

SOLUTION NOTE

Row-by-row DP. Check each row configuration is valid (no broken seats, no adjacent) and compatible with previous row.

Reveal reference solution +

pythonREFERENCE

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

    def valid_row(row_idx, mask):
        for j in range(n):
            if mask & (1 << j):
                if seats[row_idx][j] == '#':
                    return False
                if j > 0 and (mask & (1 << (j - 1))):
                    return False
        return True

    def compatible(prev_mask, curr_mask):
        for j in range(n):
            if curr_mask & (1 << j):
                if j > 0 and (prev_mask & (1 << (j - 1))):
                    return False
                if j < n - 1 and (prev_mask & (1 << (j + 1))):
                    return False
        return True

    @cache
    def dp(row, prev_mask):
        if row == m:
            return 0
        best = 0
        for mask in range(1 << n):
            if valid_row(row, mask) and compatible(prev_mask, mask):
                best = max(best, bin(mask).count('1') + dp(row + 1, mask))
        return best

    return dp(0, 0)

TimeO(m × 4^n)

SpaceO(m × 2^n)

Open on LeetCode ↗