1386. Cinema Seat Allocation
Asked at Meta
Difficulty
Medium
Time
O(R)
Space
O(R)
Pattern
Array
Companies
1
Problem
A cinema has n rows of seats. Every row has exactly 10 seats, numbered 1 to 10 from left to right. Some seats are already taken; you get them as a list of [row, seat] pairs.
You must seat four-person groups. A group must sit in the same row and in four seats that are next to each other. Only three blocks are allowed: seats 2-5, seats 4-7, or seats 6-9. A block is usable only if all four of its seats are free. Each seat can hold at most one group, so two groups in the same row must use blocks that do not overlap.
Return the maximum number of groups you can seat. Note that n can be as large as 10^9, so you cannot loop over every row — only rows that appear in the reserved list need a closer look.
Three allowed blocks in one row
Constraints
- ●
1 <= n <= 10^9 - ●
1 <= reservedSeats.length <= min(10 * n, 10^4) - ●
reservedSeats[i] == [rowi, seati] - ●
1 <= rowi <= n - ●
1 <= seati <= 10 - ●
All reservedSeats[i] are distinct
Examples
n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]4n = 2, reservedSeats = [[2,1],[1,8],[2,6]]2n = 4, reservedSeats = [[4,3],[1,4],[4,6],[1,7]]4Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Meta | Medium | View all Meta questions → |
How to Think About It
Brute force per row: for each of the n rows, test the left group (seats 2-5), right group (6-9), and middle group (4-7). A row with no reservations fits two families (left + right). Time O(n * 10).
Key insight: only rows that appear in the reservations list need inspection. Every other row fits 2 families automatically. Store reservations as a hash map from row number to the set of reserved seats in that row.
Middle group (4,5,6,7) matters only when left AND right are both blocked. A row with reservations seats at most 1 family unless both left and right are free (no overlap with middle). Check left first, then right, then middle as fallback.
The formula: if left free AND right free -> 2. Else if left free OR right free OR middle free -> 1. Else 0. Rows not in the reservation map get 2 automatically.
Edge cases: n can be up to 10^9 (very large), so you cannot iterate all rows. Only iterate rows that appear in reservations. The answer is 2 * (n - number of reserved rows) + sum of per-row scores.
Optimal Approach
Step 1: Build a hash map from row number to the set of reserved seats in that row.
Step 2: Initialize answer = 2 * (n - number of rows in the map). This accounts for all rows with no reservations.
Step 3: For each row in the map, compute the family count:
- Check left group (seats 2,3,4,5): if none reserved, left_count = 1
- Check right group (seats 6,7,8,9): if none reserved, right_count = 1
- If left_count + right_count == 0, check middle (4,5,6,7): if none reserved, add 1
- Otherwise add left_count + right_count
Step 4: Return the total.
Walkthrough with n=3, reservedSeats=[[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]:
- Row 1: reserved {2,3,8}. Left blocked (2,3 taken). Right: 8 taken -> blocked. Middle: 4,5,6,7 free? 4,5,6,7 none in {2,3,8} -> middle free. Score: 1.
- Row 2: reserved {6}. Left free (2,3,4,5). Right: 6 taken -> blocked. Score: 1 (left only).
- Row 3: reserved {1,10}. Left free. Right free. Score: 2.
- Rows with no reservations: 3 - 3 = 0.
- Total: 1 + 1 + 2 = 4.
Time: O(R) where R is the number of reserved seats. Space: O(R) for the hash map.
Score each reserved row, give free rows 2
What Trips People Up in Real Interviews
Iterating all n rows when n can be 10^9. Only rows in the reservations map need per-row logic. Use 2 * (n - len(reserved_rows)) for the rest.
Forgetting that a row with no reservations seats 2 families, not 1. Left (2-5) and right (6-9) are disjoint and both fit simultaneously.
Checking middle group when left or right is already free. Middle overlaps both, so it never adds beyond what left+right provide. Use middle only as a fallback when both left and right are blocked.
Confusing seat numbers. Seats are 1-indexed: left = {2,3,4,5}, right = {6,7,8,9}, middle = {4,5,6,7}. Seat 1 and 10 are never used by any family group.
Missing that the same row can appear multiple times in reservedSeats. Use a set per row to deduplicate before checking groups.
Solution Code
O(R) timedef maxNumberOfFamilies(n, reservedSeats):
rows = {}
for r, s in reservedSeats:
rows.setdefault(r, set()).add(s)
ans = 2 * (n - len(rows))
for seats in rows.values():
left = not ({2,3,4,5} & seats)
right = not ({6,7,8,9} & seats)
middle = not ({4,5,6,7} & seats)
if left and right:
ans += 2
elif left or right or middle:
ans += 1
return ansFrequently Asked Questions
What is the Cinema Seat Allocation problem?
A cinema has n rows of 10 seats each, labeled 1 through 10. Some seats are already reserved. Four-person groups want to sit together in the same row, occupying four consecutive empty seats. Count the maximum number of families that can be seated across all rows.
How do you solve Cinema Seat Allocation?
The optimal approach runs in O(R) time and O(R) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Cinema Seat Allocation?
Cinema Seat Allocation is asked at Meta. It is a medium difficulty problem.
What are common mistakes on Cinema Seat Allocation?
- Iterating all n rows when n can be 10^9. Only rows in the reservations map need per-row logic. Use `2 * (n - len(reserved_rows))` for the rest.
- Forgetting that a row with no reservations seats 2 families, not 1. Left (2-5) and right (6-9) are disjoint and both fit simultaneously.
- Checking middle group when left or right is already free. Middle overlaps both, so it never adds beyond what left+right provide. Use middle only as a fallback when both left and right are blocked.
- Confusing seat numbers. Seats are 1-indexed: left = {2,3,4,5}, right = {6,7,8,9}, middle = {4,5,6,7}. Seat 1 and 10 are never used by any family group.
- Missing that the same row can appear multiple times in reservedSeats. Use a set per row to deduplicate before checking groups.