Cinema Seat Allocation

LeetCode 1487 | Difficulty: Medium

Medium

Problem Description

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.

Topics: Array, Hash Table, Greedy, Bit Manipulation

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Greedy

At each step, make the locally optimal choice. The challenge is proving the greedy choice leads to a global optimum. Look for: can I sort by some criterion? Does choosing the best option now ever hurt future choices?

When to use

Interval scheduling, activity selection, minimum coins (certain denominations), Huffman coding.

Bit Manipulation

Operate directly on binary representations. Key operations: AND (&), OR (|), XOR (^), NOT (~), shifts (<<, >>). XOR is especially useful: a ^ a = 0, a ^ 0 = a.

When to use

Finding unique elements, power of 2 checks, subset generation, toggling flags.

---

Solutions

Solution 1: C# (Best: 391 ms)

Metric	Value
Runtime	391 ms
Memory	50.2 MB
Date	2022-02-02

Solution

public class Solution {
    public int MaxNumberOfFamilies(int n, int[][] reservedSeats) {
        Dictionary<int, List<int>> d = new Dictionary<int, List<int>>();
    foreach (var seat in reservedSeats)
    {
        if (d.ContainsKey(seat[0]))
            d[seat[0]].Add(seat[1]);
        else
            d.Add(seat[0], new List<int>() { seat[1] });
    }
    int result = (n - d.Count) * 2;
    List<int> option1 = new List<int>() { 2, 3, 4, 5 };
    List<int> option2 = new List<int>() { 6, 7, 8, 9 };
    List<int> option3 = new List<int>() { 4, 5, 6, 7 };

    foreach (var nums in d.Values)
    {
        bool flag = false;
        if (!option1.Where(x => nums.Contains(x)).Any())
        {
            result++;
            flag = true;
        }
        if (!option2.Where(x => nums.Contains(x)).Any())
        {
            result++;
            flag = true;
        }
        if (!flag && !option3.Where(x => nums.Contains(x)).ToList().Any())
        {
            result++;

        }
    }
    return result;
    }
}

📜 1 more C# submission(s)

Submission (2022-02-02) — 515 ms, 51.4 MB

public class Solution {
    public int MaxNumberOfFamilies(int n, int[][] reservedSeats) {
        Dictionary<int, List<int>> d = new Dictionary<int, List<int>>();
    foreach (var seat in reservedSeats)
    {
        if (d.ContainsKey(seat[0]))
            d[seat[0]].Add(seat[1]);
        else
            d.Add(seat[0], new List<int>() { seat[1] });
    }
    int result = (n - d.Count) * 2;
    List<int> option1 = new List<int>() { 2, 3, 4, 5 };
    List<int> option2 = new List<int>() { 6, 7, 8, 9 };
    List<int> option3 = new List<int>() { 4, 5, 6, 7 };

    foreach (var nums in d.Values)
    {
        bool flag = false;
        if (option1.Where(x => nums.Contains(x)).ToList().Count == 0)
        {
            result++;
            flag = true;
        }
        if (option2.Where(x => nums.Contains(x)).ToList().Count == 0)
        {
            result++;
            flag = true;
        }
        if (!flag && option3.Where(x => nums.Contains(x)).ToList().Count == 0)
        {
            result++;

        }
    }
    return result;
    }
}

---

Complexity Analysis

Approach	Time	Space
Hash Map	$O(n)$	$O(n)$
Bit Manipulation	$O(n) or O(1)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Note you can allocate at most two families in one row.

Hint 2: Greedily check if you can allocate seats for two families, one family or none.

Hint 3: Process only rows that appear in the input, for other rows you can always allocate seats for two families.