Scale Engineer

Cinema Seat Allocation

Med
#1284Time: 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).2 companies
Patterns
GreedyBit Manipulation
Data structures
ArrayHash Table
Companies
ZohoGeico

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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

Complexity

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

Trade-offs

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.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem