# Cinema Seat Allocation
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/cinema-seat-allocation)
Canonical: https://scaleengineer.com/dsa/problems/cinema-seat-allocation
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array, Hash Table
**Companies:** [Zoho](https://scaleengineer.com/companies/zoho), [Geico](https://scaleengineer.com/companies/geico)
---
## Problem
![](https://assets.glich.co/dsa/cinema-seat-allocation/image0.png)

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:**

![](https://assets.glich.co/dsa/cinema-seat-allocation/image1.png)

**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.

# Approaches
## Sorting and Processing by Row
A key observation is that the number of rows `n` can be enormous, but the number of reserved seats is relatively small. This implies that most rows are completely empty, and each empty row can accommodate two four-person families. Therefore, we only need to focus on the rows that have reservations and calculate the rest mathematically.

This approach begins by sorting the `reservedSeats` array by row number. This allows us to process all reservations for a given row contiguously. We can then iterate through the sorted array, calculating the number of families for each unique row with reservations, and also accounting for the large blocks of empty rows between them.
**Time:** O(R log R), where R is the number of reserved seats. The dominant operation is sorting the `reservedSeats` array. The subsequent iteration through the sorted array takes O(R) time. · **Space:** O(log R) or O(R), where R is the number of reserved seats. This space is used by the sorting algorithm. The space used to store seats for a single row is constant (at most 10).
**Pros:** Avoids the overhead of a HashMap data structure.; Processes rows in a sequential and predictable order.
**Cons:** The time complexity is dominated by the sorting step, making it less efficient than a linear-time HashMap approach.; The logic to handle the gaps between rows, the first reserved row, and the rows after the last reservation can be complex to implement correctly.
### Explanation
The core of this method is to process rows sequentially. After sorting `reservedSeats` by row number, we can iterate through it. We maintain a pointer to the `lastProcessedRow`.

When we encounter a reservation for a `currentRow` that is different from the `lastProcessedRow`, we know two things: we have finished processing `lastProcessedRow`, and there is a gap of `currentRow - lastProcessedRow - 1` empty rows. Each of these empty rows contributes 2 families. We add this to our total.

Then, we gather all reservations for the `currentRow`. Based on which seats (2-9) are taken, we determine how many families can be placed. The three possible placements are seats `[2,3,4,5]`, `[4,5,6,7]`, and `[6,7,8,9]`. 
- If seats `[2,3,4,5]` and `[6,7,8,9]` are both free, we can place 2 families.
- Otherwise, if any of the three placements are free, we can place 1 family.
- Otherwise, we place 0 families.

We add this count to our total and update `lastProcessedRow`. This process repeats until all reservations are handled. Finally, we account for any empty rows between the very last reserved row and `n`.

```java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
        if (reservedSeats.length == 0) {
            return 2 * n;
        }

        Arrays.sort(reservedSeats, (a, b) -> Integer.compare(a[0], b[0]));

        int totalFamilies = 0;
        int lastRow = 0;
        int i = 0;

        while (i < reservedSeats.length) {
            int currentRow = reservedSeats[i][0];
            
            // Add families from empty rows between the last processed row and current one
            if (currentRow > lastRow + 1) {
                totalFamilies += 2 * (currentRow - lastRow - 1);
            }

            Set<Integer> reservedInRow = new HashSet<>();
            int temp_i = i;
            while (temp_i < reservedSeats.length && reservedSeats[temp_i][0] == currentRow) {
                reservedInRow.add(reservedSeats[temp_i][1]);
                temp_i++;
            }

            boolean leftPossible = true;
            boolean middlePossible = true;
            boolean rightPossible = true;

            for (int seat : reservedInRow) {
                if (seat >= 2 && seat <= 5) leftPossible = false;
                if (seat >= 4 && seat <= 7) middlePossible = false;
                if (seat >= 6 && seat <= 9) rightPossible = false;
            }

            if (leftPossible && rightPossible) {
                totalFamilies += 2;
            } else if (leftPossible || middlePossible || rightPossible) {
                totalFamilies += 1;
            }

            lastRow = currentRow;
            i = temp_i;
        }

        // Add families for empty rows after the last reserved row
        if (n > lastRow) {
            totalFamilies += 2 * (n - lastRow);
        }

        return totalFamilies;
    }
}
```
### Algorithm
1. Sort the `reservedSeats` array based on the row number. This allows processing reservations for each row together.
2. Initialize `totalFamilies` to 0. Also, keep track of the `lastProcessedRow` (initially 0) to calculate gaps of empty rows.
3. Iterate through the sorted `reservedSeats` array, processing one row at a time.
4. For each new row `currentRow` encountered:
    a. Calculate the number of fully empty rows between `lastProcessedRow` and `currentRow`. For each empty row, add 2 to `totalFamilies`.
    b. Collect all reservations for `currentRow`.
    c. Determine the number of families (0, 1, or 2) that can be seated in `currentRow` based on its specific reservations.
    d. Add this number to `totalFamilies`.
    e. Update `lastProcessedRow` to `currentRow`.
5. After the loop finishes, calculate the families for the remaining empty rows from `lastProcessedRow` up to `n` and add them to `totalFamilies`.
6. Return the final count.

## Optimal HashMap + Bitmasking
This approach is the most efficient as it processes the reservations in linear time. It avoids the `O(R log R)` cost of sorting by using a `HashMap` to group the reserved seats by row. This allows us to instantly access all reservations for any given row.

The strategy is to first calculate the number of families that can be seated in all the completely empty rows. Then, we iterate through only the rows that have reservations (the keys of our map) and calculate the number of families for each, adding them to the total. This perfectly handles the problem's constraints where `n` is large but the number of reservations is small.
**Time:** O(R), where R is the number of reserved seats. Populating the HashMap takes O(R), and iterating through its entries takes O(U), where U is the number of unique rows with reservations (U <= R). · **Space:** O(U), where U is the number of unique rows with reservations (`U <= R`). This space is required for the HashMap.
**Pros:** Optimal time complexity of O(R), making it very fast for the given constraints.; The logic is clean and directly maps to the problem structure (handling empty and non-empty rows separately).; Using a bitmask for seat representation is highly efficient in both time and space for checking placements.
**Cons:** Requires extra space to store the HashMap, proportional to the number of unique rows with reservations.
### Explanation
We can create a `HashMap<Integer, Integer>` where the key is the row number and the value is a bitmask representing the occupied seats in that row. We only care about seats 2 through 9 for placing families. An 8-bit integer is sufficient to represent the state of these seats.

- Seat 2 can map to bit 0, seat 3 to bit 1, ..., and seat 9 to bit 7.

We iterate through `reservedSeats`. For each `[row, seat]`, we update the bitmask for that `row` in the map. Seats 1 and 10 are ignored as they don't affect any of the three possible 4-person groupings.

After building the map, we calculate the total families. The number of rows with reservations is `map.size()`. The number of empty rows is `n - map.size()`. These empty rows contribute `2 * (n - map.size())` families.

Then, we iterate through the values (the bitmasks) in our map. For each row's mask, we check the three placement possibilities:
- **Left group `[2,3,4,5]`**: Check if bits 0-3 are set in the mask.
- **Middle group `[4,5,6,7]`**: Check if bits 2-5 are set.
- **Right group `[6,7,8,9]`**: Check if bits 4-7 are set.

Based on these checks, we add 0, 1, or 2 to our total for that specific row. This combination gives the final answer.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
        Map<Integer, Integer> rowToMask = new HashMap<>();

        for (int[] seat : reservedSeats) {
            int row = seat[0];
            int col = seat[1];
            // We only care about seats 2 through 9
            if (col >= 2 && col <= 9) {
                // col 2 -> bit 1, col 3 -> bit 2, ..., col 9 -> bit 8
                int mask = 1 << (col - 2);
                rowToMask.put(row, rowToMask.getOrDefault(row, 0) | mask);
            }
        }

        // Start with max families from rows that have NO reservations.
        int totalFamilies = 2 * (n - rowToMask.size());

        // Define masks for the three possible group placements
        // Seats 2,3,4,5 -> 0b00001111
        int leftGroup = 0b00001111;
        // Seats 4,5,6,7 -> 0b00111100
        int middleGroup = 0b00111100;
        // Seats 6,7,8,9 -> 0b11110000
        int rightGroup = 0b11110000;

        // Add families from rows that HAVE reservations.
        for (int mask : rowToMask.values()) {
            boolean canPlaceLeft = (mask & leftGroup) == 0;
            boolean canPlaceMiddle = (mask & middleGroup) == 0;
            boolean canPlaceRight = (mask & rightGroup) == 0;

            if (canPlaceLeft && canPlaceRight) {
                totalFamilies += 2;
            } else if (canPlaceLeft || canPlaceMiddle || canPlaceRight) {
                totalFamilies += 1;
            }
        }

        return totalFamilies;
    }
}
```
### Algorithm
1. The total number of families is the sum of families in empty rows plus the sum of families in rows with reservations.
2. Start by calculating the maximum possible families assuming all `n` rows are empty: `2 * n`.
3. Use a `HashMap` to group all reserved seats by their row number. The key is the row number, and the value can be a `Set` of reserved seats or a more optimized bitmask.
4. Iterate through the `HashMap`. Each entry represents a row that is *not* empty. For each such row, we had initially added 2 to our total. We now need to adjust this.
5. For each reserved row, calculate the actual number of families (`k`, which can be 0, 1, or 2) that can be seated.
6. The initial assumption for this row was 2 families. The actual is `k`. So, we subtract the difference `(2 - k)` from our total.
7. After iterating through all reserved rows and making adjustments, the final result is the maximum number of families.

An alternative and simpler calculation:
1. Group reserved seats by row using a `HashMap`.
2. The number of empty rows is `n - map.size()`. The contribution from these is `2 * (n - map.size())`.
3. Initialize `totalFamilies` with this value.
4. Iterate through the map. For each reserved row, calculate the families `k` (0, 1, or 2) and add `k` to `totalFamilies`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxNumberOfFamilies(int n, vector<vector<int>> &reservedSeats) {
    unordered_map<int, int> d;
    for (auto &e : reservedSeats) {
      int i = e[0], j = e[1];
      d[i] |= 1 << (10 - j);
    }
    int masks[3] = {0b0111100000, 0b0000011110, 0b0001111000};
    int ans = (n - d.size()) * 2;
    for (auto &[_, x] : d) {
      for (int &mask : masks) {
        if ((x & mask) == 0) {
          x |= mask;
          ++ans;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
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

```