Cinema Seat Allocation solution and explanation
9 more videos on this problem
Cinema Seat Allocation (Leetcode 1386)Coding Interviews · 11:32 · 5K views
Cinema Seat Allocation | Leetcode #1386Techdose · 14:57 · 3K views
LeetCode 1386 | Cinema Seat AllocationTech Traversal · 22:39 · 2K views
1386. Cinema Seat Allocation | LEETCODE MEDIUMcode Explainer · 12:35 · 2K views
Leetcode 1386. Cinema Seat Allocation (Medium)onepunchcoder · 7:08 · 2K views
LeetCode 1386 | Cinema Seat Allocation | HashMap | JavaSleepy Cracker · 10:00 · 1K views
Leetcode--1386 cinema seat allocation (Greedy)You Wu · 10:42 · 869 views
小飞羊 LeetCode 1386. Cinema Seat Allocation - 套路得人薪C++Willy小飞羊 DJ · 5:06 · 496 views
[ LeetCode ] 1386. 🍿 Cinema Seat Allocation 📽️ - Kotlin idiomatic wayBTYT Tech Library · 7:34 · 126 views
LeetCode 1386 Cinema Seats Allocation - Medium - Java SolutionTech Talk · 23:08 · 63 views
The problem
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^91 <= reservedSeats.length <= min(10*n, 10^4)reservedSeats[i].length == 21 <= reservedSeats[i][0] <= n1 <= reservedSeats[i][1] <= 10- All
reservedSeats[i]are distinct.
Approach overview
Problem Overview: A cinema has n rows with 10 seats per row. Some seats are already reserved. A family of four must sit together in one of three valid blocks: [2,3,4,5], [4,5,6,7], or [6,7,8,9]. The task is to compute the maximum number of families that can be seated without breaking these constraints.
The key observation: each row can normally hold two families (left block 2-5 and right block 6-9). Reserved seats only affect the rows where they appear, so you never need to simulate all n rows when n can be as large as 1e9. Instead, track only rows that contain reservations using a hash table.
Approach 1: Greedy Approach Using Logical Checks (O(r) time, O(r) space)
Group reserved seats by row using a map. For each affected row, check whether the three valid family blocks are free. Use simple logical checks to see if seats in ranges 2-5, 4-7, or 6-9 contain any reservation. If both left and right blocks are free, place two families. Otherwise check if the middle block 4-7 is free and place one family if possible. Rows without reservations automatically contribute two families. This approach relies on direct seat checks with an array or set lookup and works well because each row has only a constant number of seat groups to evaluate.
Approach 2: Bitmask Representation for Each Row (O(r) time, O(r) space)
Instead of storing seat numbers directly, encode reserved seats for each row as a bitmask. Each bit represents whether a seat from 2 to 9 is occupied. Bitwise AND operations quickly test whether a candidate family block conflicts with reservations. Precompute masks for the three valid seat groups (2-5, 4-7, 6-9). For each row mask, check conflicts using bit operations like (mask & groupMask) == 0. Bitmasks make the checks extremely fast and compact, which is why this solution often appears in competitive programming and bit manipulation interview problems.
Recommended for interviews: The greedy row-by-row check is usually the first solution interviewers expect because it clearly models the seating rules. The bitmask version demonstrates deeper optimization and familiarity with low-level operations. Both achieve O(r) time where r is the number of reserved seats (or rows containing reservations), which is optimal since only those rows need processing.
Approach 1: Bitmask Representation for Each Row
This approach models each row using a bitmask representation where each of the 10 seats in a row is represented by a bit. A bit is set if the corresponding seat is reserved. By doing this, you can efficiently determine the possible configurations for placing groups of four seats, which are specific patterns in the bitmask. You can then count the maximum number of 4-person groups that can be seated in each row based on the bitmask state of that row. Focus on the segments: (2,3,4,5), (4,5,6,7), and (6,7,8,9).
def maxNumberOfFamilies(n, reservedSeats):
from collections import defaultdict
reserved_map = defaultdict(int)
for row, col in reservedSeats:
reserved_map[row] |= 1 << (col - 1)
count = 0
for _ in range(n):
count += 2 # Allocate two full block spaces per row
for row_bitmask in reserved_map.values():
possible = 0
# Bitmask for (2, 3, 4, 5), (4, 5, 6, 7), (6, 7, 8, 9)
if not (row_bitmask & 0b0000001111):
possible += 1
if not (row_bitmask & 0b0000111100):
possible += 1
if not (row_bitmask & 0b1111000000):
possible += 1
if possible == 0:
count -= 2 # No groups can fit
elif possible <= 2:
count -= 1 # Only one or two groups can fit
return countimport java.util.HashMap;
public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
HashMap<Integer, Integer> reservedMap = new HashMap<>();
for (int[] seat : reservedSeats) {
reservedMap.put(seat[0], reservedMap.getOrDefault(seat[0], 0) | (1 << (seat[1] - 1)));
}
int totalGroups = (n - reservedMap.size()) * 2; // Default two groups per row if unreserved
for (int rowBitmask : reservedMap.values()) {
int possible = 0;
// Bitmask for (2, 3, 4, 5), (4, 5, 6, 7), (6, 7, 8, 9)
if ((rowBitmask & 0b0000111100) == 0) possible += 1;
if ((rowBitmask & 0b0000001111) == 0) possible += 1;
if ((rowBitmask & 0b1111000000) == 0) possible += 1;
if (possible == 0) {
totalGroups -= 2;
} else if (possible < 2) {
totalGroups -= 1;
}
}
return totalGroups;
}#include <unordered_map>
#include <vector>
using namespace std;
int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
unordered_map<int, int> reservedMap;
for (const auto& seat : reservedSeats) {
reservedMap[seat[0]] |= (1 << (seat[1] - 1));
}
int totalGroups = (n - reservedMap.size()) * 2;
for (const auto& [row, bitmask] : reservedMap) {
int possible = 0;
if ((bitmask & 0b0000111100) == 0) possible += 1;
if ((bitmask & 0b0000001111) == 0) possible += 1;
if ((bitmask & 0b1111000000) == 0) possible += 1;
if (possible == 0) {
totalGroups -= 2;
} else if (possible < 2) {
totalGroups -= 1;
}
}
return totalGroups;
}const maxNumberOfFamilies = function(n, reservedSeats) {
const reservedMap = new Map();
for (const [row, col] of reservedSeats) {
if (!reservedMap.has(row)) {
reservedMap.set(row, 0);
}
reservedMap.set(row, reservedMap.get(row) | (1 << (col - 1)));
}
let totalGroups = (n - reservedMap.size) * 2;
for (const bitmask of reservedMap.values()) {
let possible = 0;
if ((bitmask & 0b0000111100) === 0) possible++;
if ((bitmask & 0b0000001111) === 0) possible++;
if ((bitmask & 0b1111000000) === 0) possible++;
if (possible === 0) {
totalGroups -= 2;
} else if (possible < 2) {
totalGroups -= 1;
}
}
return totalGroups;
};using System.Collections.Generic;
public class Solution {
public int MaxNumberOfFamilies(int n, int[][] reservedSeats) {
var reservedMap = new Dictionary<int, int>();
foreach (var seat in reservedSeats) {
if ((!reservedMap.ContainsKey(seat[0]))) {
reservedMap[seat[0]] = 0;
}
reservedMap[seat[0]] |= 1 << (seat[1] - 1);
}
int totalGroups = (n - reservedMap.Count) * 2;
foreach (var bitmask in reservedMap.Values) {
int possible = 0;
if ((bitmask & 0b0000111100) == 0) possible++;
if ((bitmask & 0b0000001111) == 0) possible++;
if ((bitmask & 0b1111000000) == 0) possible++;
if (possible == 0) {
totalGroups -= 2;
}
else if (possible < 2) {
totalGroups -= 1;
}
}
return totalGroups;
}
}This implementation uses a dictionary to store reserved seat information for each row, where the key is the row number and the value is a bitmask indicating the reserved seats. It then calculates the maximum number of four-person groups that can fit in each row by checking which of the specified seat configurations are available.
Time Complexity: O(m), where m is the length of the reservedSeats list. Space Complexity: O(m) for storing the reserved seat information for each row.
Approach 2: Greedy Approach Using Logical Checks
This approach uses logical conditions based on seat availability for every row and assesses possible seating blocks within each row independently. Rows without reserved seats can instantly allocate two groups. For rows with reserved seats, logical checks are performed to ascertain feasible places to position groups of four, mainly positions: (2-5), (4-7), and (6-9).
def maxNumberOfFamilies(n, reservedSeats):
rowReservations = {}
for r, c in reservedSeats:
if r not in rowReservations:
rowReservations[r] = set()
rowReservations[r].add(c)
maxGroups = 2 * (n - len(rowReservations)) # Rows without reserved seats can accommodate 2 groups
for reserved in rowReservations.values():
groupCount = 0
if all(seat not in reserved for seat in (2, 3, 4, 5)):
groupCount += 1
if all(seat not in reserved for seat in (4, 5, 6, 7)) and groupCount == 0:
groupCount += 1 # Only add one group for 4-7 if no other block
if all(seat not in reserved for seat in (6, 7, 8, 9)):
groupCount += 1
maxGroups += min(groupCount, 2)
return maxGroupsimport java.util.HashSet;
import java.util.HashMap;
public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
HashMap<Integer, HashSet<Integer>> rowReservations = new HashMap<>();
for (int[] seat : reservedSeats) {
rowReservations.computeIfAbsent(seat[0], k -> new HashSet<>()).add(seat[1]);
}
int maxGroups = 2 * (n - rowReservations.size());
for (HashSet<Integer> reserved : rowReservations.values()) {
int groupCount = 0;
if (!reserved.contains(2) && !reserved.contains(3) &&
!reserved.contains(4) && !reserved.contains(5)) {
groupCount++;
}
if (!reserved.contains(4) && !reserved.contains(5) &&
!reserved.contains(6) && !reserved.contains(7) && groupCount == 0) {
groupCount++;
}
if (!reserved.contains(6) && !reserved.contains(7) &&
!reserved.contains(8) && !reserved.contains(9)) {
groupCount++;
}
maxGroups += Math.min(groupCount, 2);
}
return maxGroups;
}#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
unordered_map<int, unordered_set<int>> rowReservations;
for (const auto& seat : reservedSeats) {
rowReservations[seat[0]].insert(seat[1]);
}
int maxGroups = 2 * (n - rowReservations.size());
for (const auto& row : rowReservations) {
const unordered_set<int>& reserved = row.second;
int groupCount = 0;
if (!reserved.count(2) && !reserved.count(3) &&
!reserved.count(4) && !reserved.count(5)) {
groupCount++;
}
if (!reserved.count(4) && !reserved.count(5) &&
!reserved.count(6) && !reserved.count(7) && groupCount == 0) {
groupCount++;
}
if (!reserved.count(6) && !reserved.count(7) &&
!reserved.count(8) && !reserved.count(9)) {
groupCount++;
}
maxGroups += min(groupCount, 2);
}
return maxGroups;
}const maxNumberOfFamilies = (n, reservedSeats) => {
const rowReservations = new Map();
for (const [r, c] of reservedSeats) {
if (!rowReservations.has(r)) {
rowReservations.set(r, new Set());
}
rowReservations.get(r).add(c);
}
let maxGroups = 2 * (n - rowReservations.size);
for (const reserved of rowReservations.values()) {
let groupCount = 0;
if (![2, 3, 4, 5].some(seat => reserved.has(seat))) {
groupCount++;
}
if (![4, 5, 6, 7].some(seat => reserved.has(seat)) && groupCount === 0) {
groupCount++;
}
if (![6, 7, 8, 9].some(seat => reserved.has(seat))) {
groupCount++;
}
maxGroups += Math.min(groupCount, 2);
}
return maxGroups;
};using System.Collections.Generic;
public class Solution {
public int MaxNumberOfFamilies(int n, int[][] reservedSeats) {
var rowReservations = new Dictionary<int, HashSet<int>>();
foreach (var seat in reservedSeats) {
if (!rowReservations.ContainsKey(seat[0])) {
rowReservations[seat[0]] = new HashSet<int>();
}
rowReservations[seat[0]].Add(seat[1]);
}
int maxGroups = 2 * (n - rowReservations.Count);
foreach (var reserved in rowReservations.Values) {
int groupCount = 0;
if (!reserved.Contains(2) && !reserved.Contains(3) &&
!reserved.Contains(4) && !reserved.Contains(5)) {
groupCount++;
}
if (!reserved.Contains(4) && !reserved.Contains(5) &&
!reserved.Contains(6) && !reserved.Contains(7) && groupCount == 0) {
groupCount++;
}
if (!reserved.Contains(6) && !reserved.Contains(7) &&
!reserved.Contains(8) && !reserved.Contains(9)) {
groupCount++;
}
maxGroups += Math.Min(groupCount, 2);
}
return maxGroups;
}
}This implementation starts by mapping reserved seats per row. It employs logical checks to decide whether rows can fit groups of four in the specific (2-5), (4-7), or (6-9) seat blocks, then updates the maximum groups count per row accordingly.
Time Complexity: O(m), where m represents the reserved seat array size. Space Complexity: O(m), due to processing and storing the reserved seats by row.
Approach 3: 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.
We traverse reservedSeats, for each seat (i, j), we add the state of the j-th seat (corresponding to the 10-j bit in the lower bits) to d[i].
For rows that do not appear in the hash table d, we can arrange 2 families arbitrarily, so the initial answer is (n - len(d)) times 2.
Next, we traverse the state of each row in the hash table. For each row, we try to arrange the situations 1234, 5678, 3456 in turn. If a situation can be arranged, we add 1 to the answer.
After the traversal, we get the final answer.
The time complexity is O(m), and the space complexity is O(m). Where m is the length of reservedSeats.
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;
}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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Bitmask Representation for Each Row | Time Complexity: O(m), where m is the length of the reservedSeats list. Space Complexity: O(m) for storing the reserved seat information for each row. |
| Greedy Approach Using Logical Checks | Time Complexity: O(m), where m represents the reserved seat array size. Space Complexity: O(m), due to processing and storing the reserved seats by row. |
| Hash Table + Bit Manipulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Logical Seat Checks | O(r) | O(r) | Best for readability and interviews when you want a clear rule-based solution |
| Bitmask Representation per Row | O(r) | O(r) | Preferred when optimizing seat checks with fast bit operations |
Frequently asked questions
Is Cinema Seat Allocation easy or hard?
Cinema Seat Allocation is classified as a medium difficulty problem. The challenge comes from recognizing that only three seat groups matter and that rows without reservations can be counted immediately, reducing the problem to simple greedy or bitmask checks.
Cinema Seat Allocation Python/Java solution
Python, Java, C++, C#, and JavaScript implementations usually follow the same structure: build a map of reserved seats by row, check the valid seat blocks, and count the number of families per row. The bitmask variant replaces seat lists with integer masks for faster checks.
How to solve Cinema Seat Allocation in O(n)?
Store reserved seats grouped by row using a hash table. For each row, check the availability of the three valid family seat groups (2-5, 4-7, 6-9). Rows without reservations allow two families immediately. Each row requires constant checks, giving overall O(r) time.
What is the best approach for Cinema Seat Allocation?
The most practical solution uses a greedy row-by-row check with a hash map storing reserved seats per row. For each row, verify whether the seat blocks 2-5, 4-7, and 6-9 are free. This runs in O(r) time where r is the number of reserved seats and avoids processing all n rows when n can be very large.
Is Cinema Seat Allocation asked at Google/Amazon/Meta?
Cinema Seat Allocation is a common medium-level interview problem involving greedy reasoning and bit manipulation. Variants of similar seat allocation or interval blocking problems have appeared in interviews at large tech companies such as Amazon and Google.
What data structure is used in Cinema Seat Allocation?
The typical implementation uses a hash table (map) to group reserved seats by row. Many optimized solutions also use bitmasks to represent seat occupancy and perform constant-time checks with bitwise operations.
What is the time complexity of Cinema Seat Allocation?
The optimal solutions run in O(r) time and O(r) space, where r is the number of reserved seats or rows containing reservations. Only rows that appear in the reservation list require processing, while all other rows contribute two families automatically.