How hard is LeetCode 1349. Maximum Students Taking Exam?

LeetCode 1349. Maximum Students Taking Exam is rated Hard on LeetCode.

What is the time complexity of LeetCode 1349. Maximum Students Taking Exam?

The Python solution on this page runs in O(4^n \times n \times m).

What is the space complexity of LeetCode 1349. Maximum Students Taking Exam?

The Python solution on this page uses O(2^n \times m) auxiliary space.

What topics does LeetCode 1349. Maximum Students Taking Exam cover?

LeetCode 1349. Maximum Students Taking Exam is tagged Bit Manipulation, Array, Dynamic Programming, Bitmask and Matrix on LeetCode.

Maximum Students Taking Exam — LeetCode 1349 Python Solution

HardBit ManipulationArrayDynamic ProgrammingBitmaskMatrix

Problem: #1349
Pattern: Bit Manipulation
Reading time: 5 min
Source: leetcode.com

The 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.

Example

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

Python solution

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)

Complexity

Measure	Complexity
Time	O(4^n \times n \times m)
Space	O(2^n \times m) auxiliary

Pattern: Bit Manipulation

Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 1349. Maximum Students Taking Exam is filed here because LeetCode tags it Bit Manipulation and Bitmask, which is the vocabulary this hub collects.

The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1349. Maximum Students Taking Exam?: LeetCode 1349. Maximum Students Taking Exam is rated Hard on LeetCode.
What is the time complexity of LeetCode 1349. Maximum Students Taking Exam?: The Python solution on this page runs in O(4^n \times n \times m).
What is the space complexity of LeetCode 1349. Maximum Students Taking Exam?: The Python solution on this page uses O(2^n \times m) auxiliary space.
What topics does LeetCode 1349. Maximum Students Taking Exam cover?: LeetCode 1349. Maximum Students Taking Exam is tagged Bit Manipulation, Array, Dynamic Programming, Bitmask and Matrix on LeetCode.