#1386

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Cinema Seat Allocation

Determine the maximum number of four-person groups that can be seated in a cinema using array scanning and hash lookup efficiently.

array hash table greedy bit manipulation

Problem Statement

You are given a cinema with n rows, each row containing ten seats numbered 1 to 10. Some seats are already reserved, represented as an array reservedSeats where reservedSeats[i] = [row, seat] marks a reserved position.

Return the maximum number of four-person groups that can be seated. Each group must occupy four adjacent seats in the same row. Seats separated by an aisle are not considered adjacent except for the middle split case, where two people can sit on either side of an aisle.

Examples

Example 1

Input: n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]

Output: 4

The figure above shows the optimal allocation for four groups, where seats mark with blue are already reserved and contiguous seats mark with orange are for one group.

Example 2

Input: n = 2, reservedSeats = [[2,1],[1,8],[2,6]]

Output: 2

Example details omitted.

Example 3

Input: n = 4, reservedSeats = [[4,3],[1,4],[4,6],[1,7]]

Output: 4

Example details omitted.

Constraints

1 <= n <= 10^9
1 <= reservedSeats.length <= min(10*n, 10^4)
reservedSeats[i].length == 2
1 <= reservedSeats[i][0] <= n
1 <= reservedSeats[i][1] <= 10
All reservedSeats[i] are distinct.

Solution Approach

Map reserved seats by row

Use a hash table to store reserved seats per row, enabling quick lookup of which seats are blocked. This allows skipping empty rows entirely and focuses checks only on rows with reservations.

Check available four-seat blocks

For each row with reservations, scan three possible blocks: left (2-5), middle (4-7), and right (6-9). Use bit masks to quickly determine if any block is fully available for a group. Count at most two groups per row.

Compute total groups efficiently

Add two for each empty row without reserved seats. For reserved rows, add one or two depending on which blocks are free. Sum these counts to get the final maximum number of four-person groups.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(R) where R is the number of rows with reserved seats, since each reserved row is scanned with constant checks; empty rows are computed directly. Space complexity is O(R) to store reserved seat positions in a hash table.

What Interviewers Usually Probe

Check if your solution handles rows with no reserved seats efficiently.
They may ask why a row cannot always hold two groups if seats are partially reserved.
Expect follow-up on using bit manipulation versus simple greedy checks for blocks.

Common Pitfalls or Variants

Common pitfalls

Ignoring the middle block split across an aisle and incorrectly counting four-person groups.
Assuming all rows with reserved seats can only fit one group without scanning possible blocks.
Iterating over n rows directly instead of leveraging hash lookup for sparse reservations.

Follow-up variants

Change the group size from four to k and adjust block checks accordingly.
Introduce variable row lengths to test adaptive array scanning strategies.
Limit reservedSeats length to small numbers but n extremely large to test hash lookup efficiency.

FAQ

What is the best way to handle large n with few reservedSeats?

Use a hash table to store only rows with reservations, skipping empty rows and computing counts directly to maintain efficiency.

Can a four-person group sit across an aisle?

Only in the middle split case (seats 4-7), where two seats can sit on each side; otherwise, aisles break adjacency.

Why use bit manipulation in this problem?

Bit masks allow fast checks of multiple contiguous seats per row to determine if a group can be seated without iterating each seat.

How many groups can one row hold?

At most two groups per row, unless reserved seats prevent one or both possible four-seat blocks.

Does this problem follow the array scanning plus hash lookup pattern?

Yes, the core approach scans potential blocks per row and uses a hash table for reserved seat lookups to avoid unnecessary iteration.

terminal

Solution

Solution 1: Hash Table + Bit Manipulation

We use a hash table $d$ to store all the reserved seats, where the key is the row number, and the value is the state of the reserved seats in that row, i.e., a binary number. The $j$-th bit being $1$ means the $j$-th seat is reserved, and $0$ means the $j$-th seat is not reserved.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        d = defaultdict(int)
        for i, j in reservedSeats:
            d[i] |= 1 << (10 - j)
        masks = (0b0111100000, 0b0000011110, 0b0001111000)
        ans = (n - len(d)) * 2
        for x in d.values():
            for mask in masks:
                if (x & mask) == 0:
                    x |= mask
                    ans += 1
        return ans

Continue Practicing

#1338 reduce array size to the half #1442 count triplets that can form two arrays of equal xor #1296 divide array in sets of k consecutive numbers