LeetCode 1386 - Cinema Seat Allocation

LeetCode Problem 1386

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Greedy, Bit Manipulation

Solution

Here is a complete, detailed technical solution guide for LeetCode 1386 - Cinema Seat Allocation in a single, comprehensive response following your formatting rules.

Problem Understanding

The problem describes a cinema with n rows, each containing exactly ten seats, labelled 1 through 10. Some of these seats are already reserved, given in the input array reservedSeats, where each element is a pair [row, seat]. The goal is to determine the maximum number of four-person groups that can be assigned to the cinema such that each group occupies four consecutive seats in the same row.

A four-person group cannot span across an aisle. In this problem, the aisles are conceptually between seats 2 and 3, 4 and 5, 6 and 7, and 8 and 9, meaning the only viable blocks for a group are seats 2-5, 4-7, and 6-9. However, groups in seats 4-7 can share the middle section to maximize usage.

The input guarantees that 1 <= n <= 10^9 and 1 <= reservedSeats.length <= min(10*n, 10^4). This implies that n can be very large, but the number of reserved seats is relatively small (at most 10,000). This is a key insight because we cannot iterate over every row directly - we must use a more efficient approach that only processes rows with reserved seats.

Edge cases include rows with no reserved seats, rows fully blocked in the middle, and rows where reserved seats are on the edges, which may still allow one group. The problem also guarantees that no seat is repeated in reservedSeats.

Approaches

The brute-force approach would iterate over every row and check every possible four-seat block for each row. For n up to 10^9, this is infeasible, even if we use just constant time per row.

The optimal approach leverages the fact that only rows with reserved seats need careful checking. Rows with no reserved seats can automatically accommodate two groups (one in seats 2-5 and another in 6-9). For rows with reserved seats, we track which seats are blocked using a bitmask, then check the three candidate blocks (2-5, 4-7, 6-9) for availability.

This observation reduces the problem from O(n) to O(reservedSeats.length) in time complexity and O(reservedSeats.length) in space, which is feasible given the constraints.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Iterates over all rows, infeasible for large n
Optimal	O(r)	O(r)	Only processes rows with reserved seats, r = len(reservedSeats)

Algorithm Walkthrough

1. Initialize a hash map reserved_map that maps a row number to a bitmask representing blocked seats.
2. For each reserved seat [row, seat], set the corresponding bit in the row's bitmask to 1. Seats are numbered 1-10, so bit 1 corresponds to seat 1, bit 2 to seat 2, etc.
3. Initialize a variable max_groups as 2 * n. This assumes all rows are free and can accommodate two groups.
4. For each row in reserved_map, check the three possible seat blocks for availability:

• Left block: seats 2-5
• Middle block: seats 4-7
• Right block: seats 6-9

Each block is represented as a mask, and we can check if row_mask & block_mask == 0 to determine availability. 5. Compute how many groups can actually be placed in that row:

• If both left and right blocks are free, the row can have 2 groups.
• If either left, middle, or right block is free, the row can have 1 group.
• If no block is free, the row has 0 groups.

6. Subtract 2 from max_groups (our initial overcount) and add the actual number of groups for the row. This ensures we adjust only rows with reservations.
7. Return max_groups.

Why it works: The invariant is that rows without reserved seats always contribute 2 groups. Rows with reservations are corrected based on actual availability, and no row is double-counted. This guarantees the maximum number of groups.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        reserved_map = defaultdict(int)
        for row, seat in reservedSeats:
            reserved_map[row] |= 1 << (seat - 1)
        
        max_groups = 2 * n
        for row_mask in reserved_map.values():
            left_block = 0b00011110   # seats 2-5
            middle_block = 0b00111100 # seats 4-7
            right_block = 0b11110000  # seats 6-9
            
            groups = 0
            if (row_mask & left_block) == 0:
                groups += 1
            if (row_mask & right_block) == 0:
                groups += 1
            if groups == 0 and (row_mask & middle_block) == 0:
                groups = 1
            
            max_groups += groups - 2  # adjust overcount for this row
        
        return max_groups

Explanation:

We first convert each reserved seat into a bitmask for its row. Then, by using bitwise AND, we can efficiently check if any seat in a candidate block is occupied. The max_groups variable is initialized assuming all rows are free, and then we adjust based on actual reserved seats. This avoids iterating through all n rows explicitly.

Go Solution

func maxNumberOfFamilies(n int, reservedSeats [][]int) int {
    reservedMap := make(map[int]int)
    for _, seat := range reservedSeats {
        row := seat[0]
        s := seat[1] - 1
        reservedMap[row] |= 1 << s
    }

    maxGroups := 2 * n
    for _, rowMask := range reservedMap {
        leftBlock := 0b00011110   // seats 2-5
        middleBlock := 0b00111100 // seats 4-7
        rightBlock := 0b11110000  // seats 6-9

        groups := 0
        if rowMask&leftBlock == 0 {
            groups++
        }
        if rowMask&rightBlock == 0 {
            groups++
        }
        if groups == 0 && rowMask&middleBlock == 0 {
            groups = 1
        }
        maxGroups += groups - 2
    }

    return maxGroups
}

Go-specific notes:

Go uses map[int]int for the reserved rows. Bitwise operations are identical to Python, and initialization of masks is simple with binary literals. There is no need to predefine array sizes since the map dynamically grows.

Worked Examples

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

Row	Reserved mask	Left free?	Middle free?	Right free?	Groups
1	0b10000110	No	Yes	No	1
2	0b00100000	Yes	Yes	No	1
3	0b1000000001	Yes	Yes	Yes	2

max_groups = 2*3 = 6, adjust per row: 6 - 2 + 1 = 5? Wait carefully:

• Row 1: groups = 1 → max_groups += 1 - 2 = -1 → max_groups = 6-1 = 5
• Row 2: groups = 1 → max_groups += 1 - 2 = -1 → max_groups = 4
• Row 3: groups = 2 → max_groups += 2 - 2 = 0 → max_groups = 4

Correct output: 4.

This shows the step-by-step adjustment matches the expected output.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(r)	We iterate over each reserved seat and each row with reservations, r = len(reservedSeats) ≤ 10^4
Space	O(r)	We store a map from row number to bitmask for rows with reserved seats

All other operations are constant time per row or seat.

Test Cases

# Provided examples
assert Solution().maxNumberOfFamilies(3, [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]) == 4  # example 1
assert Solution().maxNumberOfFamilies(2, [[2,1],[1,8],[2,6]]) == 2  # example 2
assert Solution().maxNumberOfFamilies(4, [[4,3],[1,4],[4,6],[1,7]]) == 4  # example