LeetCode #1386 — MEDIUM

Cinema Seat Allocation

Move from brute-force thinking to an efficient approach using array strategy.

The Problem

Problem Statement

A cinema has n rows of seats, numbered from 1 to n and there are ten seats in each row, labelled from 1 to 10 as shown in the figure above.

Given the array reservedSeats containing the numbers of seats already reserved, for example, reservedSeats[i] = [3,8] means the seat located in row 3 and labelled with 8 is already reserved.

Return the maximum number of four-person groups you can assign on the cinema seats. A four-person group occupies four adjacent seats in one single row. Seats across an aisle (such as [3,3] and [3,4]) are not considered to be adjacent, but there is an exceptional case on which an aisle split a four-person group, in that case, the aisle split a four-person group in the middle, which means to have two people on each side.

Example 1:

Input: n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
Output: 4
Explanation: 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 3:

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

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.

Step 01

Brute Force Baseline

Problem summary: A cinema has n rows of seats, numbered from 1 to n and there are ten seats in each row, labelled from 1 to 10 as shown in the figure above. Given the array reservedSeats containing the numbers of seats already reserved, for example, reservedSeats[i] = [3,8] means the seat located in row 3 and labelled with 8 is already reserved. Return the maximum number of four-person groups you can assign on the cinema seats. A four-person group occupies four adjacent seats in one single row. Seats across an aisle (such as [3,3] and [3,4]) are not considered to be adjacent, but there is an exceptional case on which an aisle split a four-person group, in that case, the aisle split a four-person group in the middle, which means to have two people on each side.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Hash Map · Greedy · Bit Manipulation

Example 1

3
[[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]

Example 2

2
[[2,1],[1,8],[2,6]]

Example 3

4
[[4,3],[1,4],[4,6],[1,7]]

Core Insight

What unlocks the optimal approach

Note you can allocate at most two families in one row.
Greedily check if you can allocate seats for two families, one family or none.
Process only rows that appear in the input, for other rows you can always allocate seats for two families.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Upper-end input sizes

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #1386: Cinema Seat Allocation
class Solution {
    public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
        Map<Integer, Integer> d = new HashMap<>();
        for (var e : reservedSeats) {
            int i = e[0], j = e[1];
            d.merge(i, 1 << (10 - j), (x, y) -> x | y);
        }
        int[] masks = {0b0111100000, 0b0000011110, 0b0001111000};
        int ans = (n - d.size()) * 2;
        for (int x : d.values()) {
            for (int mask : masks) {
                if ((x & mask) == 0) {
                    x |= mask;
                    ++ans;
                }
            }
        }
        return ans;
    }
}

// Accepted solution for LeetCode #1386: Cinema Seat Allocation
func maxNumberOfFamilies(n int, reservedSeats [][]int) int {
	d := map[int]int{}
	for _, e := range reservedSeats {
		i, j := e[0], e[1]
		d[i] |= 1 << (10 - j)
	}
	ans := (n - len(d)) * 2
	masks := [3]int{0b0111100000, 0b0000011110, 0b0001111000}
	for _, x := range d {
		for _, mask := range masks {
			if x&mask == 0 {
				x |= mask
				ans++
			}
		}
	}
	return ans
}

# Accepted solution for LeetCode #1386: Cinema Seat Allocation
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

// Accepted solution for LeetCode #1386: Cinema Seat Allocation
#![allow(clippy::unreadable_literal)]
struct Solution;
use std::collections::HashMap;

impl Solution {
    fn max_number_of_families(n: i32, reserved_seats: Vec<Vec<i32>>) -> i32 {
        let n = n as usize;
        let mut hm: HashMap<usize, u16> = HashMap::new();
        for seat in reserved_seats {
            let i = (seat[0] - 1) as usize;
            let j = (seat[1] - 1) as usize;
            *hm.entry(i).or_default() |= 1 << j;
        }
        let mut res = 0;
        for &row_bitset in hm.values() {
            res += Self::num_of_families(row_bitset);
        }
        res += (n - hm.len()) * 2;
        res as i32
    }

    fn num_of_families(row_bitset: u16) -> usize {
        let two = 0b0111111110;
        let mid = 0b0001111000;
        let left = 0b0111100000;
        let right = 0b0000011110;
        if row_bitset & two == 0 {
            2
        } else {
            if row_bitset & mid == 0 {
                1
            } else {
                if row_bitset & left == 0 || row_bitset & right == 0 {
                    1
                } else {
                    0
                }
            }
        }
    }
}

#[test]
fn test() {
    let n = 3;
    let reserved_seats = vec_vec_i32![[1, 2], [1, 3], [1, 8], [2, 6], [3, 1], [3, 10]];
    let res = 4;
    assert_eq!(Solution::max_number_of_families(n, reserved_seats), res);
    let n = 2;
    let reserved_seats = vec_vec_i32![[2, 1], [1, 8], [2, 6]];
    let res = 2;
    assert_eq!(Solution::max_number_of_families(n, reserved_seats), res);
    let n = 4;
    let reserved_seats = vec_vec_i32![[4, 3], [1, 4], [4, 6], [1, 7]];
    let res = 4;
    assert_eq!(Solution::max_number_of_families(n, reserved_seats), res);
}

// Accepted solution for LeetCode #1386: Cinema Seat Allocation
function maxNumberOfFamilies(n: number, reservedSeats: number[][]): number {
    const d: Map<number, number> = new Map();
    for (const [i, j] of reservedSeats) {
        d.set(i, (d.get(i) ?? 0) | (1 << (10 - j)));
    }
    let ans = (n - d.size) << 1;
    const masks = [0b0111100000, 0b0000011110, 0b0001111000];
    for (let [_, x] of d) {
        for (const mask of masks) {
            if ((x & mask) === 0) {
                x |= mask;
                ++ans;
            }
        }
    }
    return ans;
}

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(m)

Space

O(m)

Approach Breakdown

EXHAUSTIVE

O(2ⁿ) time

O(n) space

Try every possible combination of choices. With n items each having two states (include/exclude), the search space is 2ⁿ. Evaluating each combination takes O(n), giving O(n × 2ⁿ). The recursion stack or subset storage uses O(n) space.

GREEDY

O(n log n) time

O(1) space

Greedy algorithms typically sort the input (O(n log n)) then make a single pass (O(n)). The sort dominates. If the input is already sorted or the greedy choice can be computed without sorting, time drops to O(n). Proving greedy correctness (exchange argument) is harder than the implementation.

Shortcut: Sort + single pass → O(n log n). If no sort needed → O(n). The hard part is proving it works.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.

Mutating counts without cleanup

Wrong move: Zero-count keys stay in map and break distinct/count constraints.

Usually fails on: Window/map size checks are consistently off by one.

Fix: Delete keys when count reaches zero.

Using greedy without proof

Wrong move: Locally optimal choices may fail globally.

Usually fails on: Counterexamples appear on crafted input orderings.

Fix: Verify with exchange argument or monotonic objective before committing.