1386. Cinema Seat Allocation LeetCode Solution

Last updated: February 23, 2025

In this guide, you will get 1386. Cinema Seat Allocation LeetCode Solution with the best time and space complexity. The solution to Cinema Seat Allocation problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Cinema Seat Allocation solution in C++
Cinema Seat Allocation solution in Java
Cinema Seat Allocation solution in Python
Additional Resources

1386. Cinema Seat Allocation LeetCode Solution image

Problem Statement of Cinema Seat Allocation

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.

Complexity Analysis

Time Complexity: O(|\texttt{reservedSeats}|)
Space Complexity: O(|\texttt{reservedSeats}|)

1386. Cinema Seat Allocation LeetCode Solution in C++

class Solution {
 public:
  int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
    int ans = 0;
    unordered_map<int, int> rowToSeats;

    for (const vector<int>& reservedSeat : reservedSeats) {
      const int row = reservedSeat[0];
      const int seat = reservedSeat[1];
      rowToSeats[row] |= 1 << (seat - 1);
    }

    for (const auto& [_, seats] : rowToSeats)
      if ((seats & 0b0111111110) == 0)
        // Can fit 2 four-person groups.
        ans += 2;
      else if ((seats & 0b0111100000) == 0 ||  // The left is not occupied.
               (seats & 0b0001111000) == 0 ||  // The middle is not occupied.
               (seats & 0b0000011110) == 0)    // The right is notoccupied.
        // Can fit 1 four-person group.
        ans += 1;

    // Any empty row can fit 2 four-person groups.
    return ans + (n - rowToSeats.size()) * 2;
  }
};
/* code provided by PROGIEZ */

1386. Cinema Seat Allocation LeetCode Solution in Java

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

    for (int[] reservedSeat : reservedSeats) {
      final int row = reservedSeat[0];
      final int seat = reservedSeat[1];
      rowToSeats.put(row, rowToSeats.getOrDefault(row, 0) | 1 << (seat - 1));
    }

    for (final int seats : rowToSeats.values())
      if ((seats & 0b0111111110) == 0)
        // Can fit 2 four-person groups.
        ans += 2;
      else if ((seats & 0b0111100000) == 0 || // The left is not occupied.
               (seats & 0b0001111000) == 0 || // The middle is not occupied.
               (seats & 0b0000011110) == 0)   // The right is notoccupied.
        // Can fit 1 four-person group.
        ans += 1;

    // Any empty row can fit 2 four-person groups.
    return ans + (n - rowToSeats.size()) * 2;
  }
}
// code provided by PROGIEZ

1386. Cinema Seat Allocation LeetCode Solution in Python

class Solution:
  def maxNumberOfFamilies(self, n: int, reservedSeats: list[list[int]]) -> int:
    ans = 0
    rowToSeats = collections.Counter()

    for row, seat in reservedSeats:
      rowToSeats[row] |= 1 << (seat - 1)

    for seats in rowToSeats.values():
      if (seats & 0b0111111110) == 0:
        # Can fit 2 four-person groups.
        ans += 2
      elif ((seats & 0b0111100000) == 0 or
            (seats & 0b0001111000) == 0 or
            (seats & 0b0000011110) == 0):
        # Can fit 1 four-person group.
        ans += 1

    # Any empty row can fit 2 four-person groups.
    return ans + (n - len(rowToSeats)) * 2
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents