Problem Description

You have a cinema with n rows of seats. Each row contains 10 seats labeled from 1 to 10. The seats are arranged such that seats 3 and 4 are separated by an aisle, as well as seats 7 and 8.

Given an array reservedSeats where reservedSeats[i] = [row, seat] indicates that the seat at position seat in row row is already reserved, you need to find the maximum number of four-person groups that can be assigned to the available seats.

A four-person group must occupy 4 adjacent seats in the same row. The valid arrangements for a four-person group in any row are:

• Seats [2, 3, 4, 5] - two people on each side of the first aisle
• Seats [4, 5, 6, 7] - all four in the middle section
• Seats [6, 7, 8, 9] - two people on each side of the second aisle

Note that while seats across an aisle (like seats 3 and 4, or seats 7 and 8) are normally not considered adjacent, there's an exception when the group is split evenly with two people on each side of the aisle.

The task is to determine the maximum number of four-person groups that can be seated given the constraints of the reserved seats. Each group must be seated together in one of the three valid configurations mentioned above.

For example, if n = 3 and reservedSeats = [[1,2], [1,3], [1,8], [2,6], [3,1], [3,10]], you need to check each row to see which four-person group configurations are still possible after accounting for the reserved seats.

Intuition

The key insight is that for each row, there are only three possible ways to seat a 4-person group: seats [2,3,4,5], seats [4,5,6,7], or seats [6,7,8,9]. This means we need to check which of these three configurations are available in each row.

Since we're dealing with seat positions and need to quickly check if certain seats are occupied, bit manipulation becomes a natural choice. We can represent each row's reservation state as a binary number where each bit corresponds to a seat (1 means reserved, 0 means available).

For rows with no reservations at all, we can always place 2 groups - either at positions [2,3,4,5] and [6,7,8,9], or any other non-overlapping combination. This gives us a starting point: if a row has no reservations, it contributes 2 groups to our answer.

The challenge is handling rows with some reserved seats. We need to check if any of the three possible group positions are completely free. The trick is to use bitmasks to represent each group configuration:

• 0b0111100000 for seats 2-5 (bits 8,7,6,5 set to 1)
• 0b0001111000 for seats 4-7 (bits 6,5,4,3 set to 1)
• 0b0000011110 for seats 6-9 (bits 4,3,2,1 set to 1)

By using bitwise AND operation between the row's reservation state and each mask, we can quickly determine if a group configuration is available (result is 0 if no overlap with reservations).

Another optimization is that we only need to track rows that have at least one reservation. Rows without any reservations can be counted directly as contributing 2 groups each, calculated as (n - number_of_rows_with_reservations) * 2.

The greedy approach of trying each configuration and marking it as used (by OR-ing with the mask) ensures we don't double-count overlapping positions while maximizing the number of groups we can place.

Learn more about Greedy patterns.

Solution Approach

We implement the solution using a hash table combined with bit manipulation to efficiently track and check seat reservations.

Step 1: Build the reservation state

We use a defaultdict(int) where each key represents a row number, and the value is a binary number representing the reservation state of that row. For each reserved seat (i, j), we set the corresponding bit by using d[i] |= 1 << (10 - j). The expression 10 - j maps seat number j to the correct bit position (seat 10 maps to bit 0, seat 1 maps to bit 9).

Step 2: Calculate base answer

Rows that don't appear in our hash table have no reservations, so we can place 2 groups in each of these rows. The number of such rows is n - len(d), giving us an initial answer of (n - len(d)) * 2.

Step 3: Define group position masks

We create three bitmasks representing the three possible 4-person group configurations:

• 0b0111100000 for seats 2-5 (left group)
• 0b0000011110 for seats 6-9 (right group)
• 0b0001111000 for seats 4-7 (middle group)

Step 4: Process rows with reservations

For each row with reservations (values in hash table d):

1. We iterate through each mask to check if that group position is available
2. Check availability using (x & mask) == 0, which returns true if none of the seats in the group are reserved
3. If a group can be placed, we mark those seats as used by x |= mask to prevent overlapping with other groups
4. Increment the answer counter for each successfully placed group

Step 5: Return the result

The algorithm greedily tries to place groups in the order of the masks. By updating x after each successful placement, we ensure that overlapping configurations like [2,3,4,5] and [4,5,6,7] aren't both counted for the same row.

The time complexity is O(m) where m is the number of reserved seats, as we process each reservation once and then iterate through rows with reservations. The space complexity is O(k) where k is the number of rows with at least one reservation.

Example Walkthrough

Let's walk through a small example with n = 3 rows and reservedSeats = [[1,2], [1,8], [2,6]].

Step 1: Build reservation state

We create a hash table to track reservations using bit manipulation:

• For [1,2]: Row 1, seat 2 → set bit at position 10-2=8 → d[1] = 0b0100000000
• For [1,8]: Row 1, seat 8 → set bit at position 10-8=2 → d[1] |= 0b0000000100 → d[1] = 0b0100000100
• For [2,6]: Row 2, seat 6 → set bit at position 10-6=4 → d[2] = 0b0000010000

Row 3 has no reservations, so it doesn't appear in our hash table.

Step 2: Calculate base answer

Rows without reservations: 3 - 2 = 1 row (Row 3) Base answer: 1 × 2 = 2 groups

Step 3: Define masks

• Left group (seats 2-5): 0b0111100000
• Right group (seats 6-9): 0b0000011110
• Middle group (seats 4-7): 0b0001111000

Step 4: Process rows with reservations

Row 1 (x = 0b0100000100):

• Check left group: 0b0100000100 & 0b0111100000 = 0b0100000000 ≠ 0 (seat 2 reserved, cannot place)
• Check right group: 0b0100000100 & 0b0000011110 = 0b0000000100 ≠ 0 (seat 8 reserved, cannot place)
• Check middle group: 0b0100000100 & 0b0001111000 = 0b0000000000 = 0 (available!)
  • Place group: x |= 0b0001111000 → x = 0b0101111100
  • Increment answer: 2 + 1 = 3

Row 2 (x = 0b0000010000):

• Check left group: 0b0000010000 & 0b0111100000 = 0b0000000000 = 0 (available!)
  • Place group: x |= 0b0111100000 → x = 0b0111110000
  • Increment answer: 3 + 1 = 4
• Check right group: 0b0111110000 & 0b0000011110 = 0b0000010000 ≠ 0 (seat 6 now occupied, cannot place)
• Check middle group: 0b0111110000 & 0b0001111000 = 0b0001110000 ≠ 0 (overlaps with left group, cannot place)

Step 5: Return result

Final answer: 4 groups

• Row 1: 1 group (middle position)
• Row 2: 1 group (left position)
• Row 3: 2 groups (no reservations)

Solution Implementation

Time and Space Complexity

Time Complexity: O(m), where m is the length of reservedSeats.

The algorithm iterates through the reservedSeats list once to build the dictionary d, which takes O(m) time. Each reservation operation involves a dictionary access and bitwise OR operation, both of which are O(1). Then, it iterates through the dictionary values (at most m unique rows) and for each value, checks against 3 masks with constant-time bitwise operations. Since there can be at most m unique rows in the dictionary, this second iteration is also O(m). Therefore, the overall time complexity is O(m) + O(m) = O(m).

Space Complexity: O(m), where m is the length of reservedSeats.

The algorithm uses a dictionary d to store the reserved seats information. In the worst case, when all reserved seats are in different rows, the dictionary will contain m entries (one for each unique row). Each entry stores a row number as the key and an integer bitmask as the value, both requiring O(1) space. Therefore, the total space complexity is O(m).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Incorrect Mask Order Leading to Suboptimal Results

One critical pitfall in this solution is the order of the masks in family_group_masks. The current implementation uses the order (left, right, middle), but this can lead to suboptimal group placement in certain scenarios.

Why this is a problem:

Consider a row where only seat 5 is reserved. With the current mask order:

1. First tries left group [2,3,4,5] - fails because seat 5 is reserved
2. Then tries right group [6,7,8,9] - succeeds and places one group
3. Finally tries middle group [4,5,6,7] - fails because seat 6 is now marked as used

However, if we had tried the middle group first, it would have failed (seat 5 reserved), then we could successfully place both left [2,3,4,5] and right [6,7,8,9] groups since seat 5 being reserved doesn't affect the left group when checking seats 2-5.

Wait, let me reconsider this example:

Actually, if seat 5 is reserved:

• Left group [2,3,4,5] - includes seat 5, so this fails
• Right group [6,7,8,9] - doesn't include seat 5, so this succeeds
• Middle group [4,5,6,7] - includes seat 5, so this fails

The real pitfall occurs when we have strategic reservations. For example, if seats 3 and 8 are reserved:

• With order (left, right, middle): left fails, right fails, middle succeeds = 1 group
• With order (middle, left, right): middle succeeds, then left and right both fail = 1 group

Actually, the more significant pitfall is not considering all possible combinations optimally.

The Real Pitfall: Greedy Approach May Miss Optimal Solutions

The greedy approach of trying masks in a fixed order can miss the optimal solution. Consider when only seat 6 is reserved:

Current approach (left, right, middle):

• Left [2,3,4,5] succeeds ✓
• Right [6,7,8,9] fails (seat 6 reserved) ✗
• Middle [4,5,6,7] fails (seat 4 and 5 already used by left group) ✗
• Result: 1 group

But if we had chosen differently:

• Skip left, try right first - fails
• Try middle [4,5,6,7] - fails (seat 6 reserved)
• Try left [2,3,4,5] - succeeds
• Actually, this also gives 1 group

The real issue is when middle group placement could prevent placing two separate groups.

Solution to the Pitfall:

Instead of using a greedy approach with a fixed order, we should check all valid combinations for each row:

def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
    reserved_by_row = defaultdict(int)
  
    for row, seat in reservedSeats:
        reserved_by_row[row] |= 1 << (10 - seat)
  
    left_mask = 0b0111100000   # seats 2-5
    right_mask = 0b0000011110  # seats 6-9
    middle_mask = 0b0001111000 # seats 4-7
  
    total_families = (n - len(reserved_by_row)) * 2
  
    for row_reservation in reserved_by_row.values():
        # Check all possible combinations
        can_place_left = (row_reservation & left_mask) == 0
        can_place_right = (row_reservation & right_mask) == 0
        can_place_middle = (row_reservation & middle_mask) == 0
      
        # Optimal strategy:
        # - If both left and right possible, place both (2 groups)
        # - Otherwise, if any single position possible, place it (1 group)
        if can_place_left and can_place_right:
            total_families += 2
        elif can_place_left or can_place_right or can_place_middle:
            total_families += 1
  
    return total_families

This approach evaluates all possibilities first and then makes the optimal choice, ensuring we don't miss better configurations due to greedy placement order.