Consecutive Available Seats II

Problem

Table: Cinema

1
2
3
4
5
6
7
8


+-------------+------+
| Column Name | Type |
+-------------+------+
| seat_id     | int  |
| free        | bool |
+-------------+------+
seat_id is an auto-increment column for this table.
Each row of this table indicates whether the ith seat is free or not. 1 means free while 0 means occupied.

Write a solution to find the length of longest consecutive sequence of available seats in the cinema.

Note:

There will always be at most one longest consecutive sequence.
If there are multiple consecutive sequences with the same length , include all of them in the output.

Return the result tableordered by first_seat_id in ascending order.

The result format is in the following example.

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


Input:
Cinema table:
+---------+------+
| seat_id | free |
+---------+------+
| 1       | 1    |
| 2       | 0    |
| 3       | 1    |
| 4       | 1    |
| 5       | 1    |
+---------+------+
Output:
+-----------------+----------------+-----------------------+
| first_seat_id   | last_seat_id   | consecutive_seats_len |
+-----------------+----------------+-----------------------+
| 3               | 5              | 3                     |
+-----------------+----------------+-----------------------+
Explanation:
* Longest consecutive sequence of available seats starts from seat 3 and ends at seat 5 with a length of 3.
Output table is ordered by first_seat_id in ascending order.

Solution

Method 1 – Window Functions and Grouping

Intuition

We want to find the length of the longest consecutive sequence of available seats (free = 1). We can use window functions to assign a group number to each consecutive block of free seats, then count the length of each group and select the maximum.

Approach

Use a window function to assign a group number to each consecutive block of free seats. This can be done by subtracting the row number from the seat_id for free seats.
Filter only free seats (free = 1).
Group by the group number and count the number of seats in each group.
Find the maximum length among all groups.
If there are multiple groups with the same maximum length, include all of them in the output.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


WITH free_seats AS (
  SELECT seat_id, free,
         seat_id - ROW_NUMBER() OVER (ORDER BY seat_id) AS grp
  FROM Cinema
  WHERE free = 1
)
SELECT COUNT(*) AS length
FROM free_seats
GROUP BY grp
HAVING COUNT(*) = (
  SELECT MAX(cnt) FROM (
    SELECT COUNT(*) AS cnt FROM free_seats GROUP BY grp
  ) t
);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


WITH free_seats AS (
  SELECT seat_id, free,
         seat_id - ROW_NUMBER() OVER (ORDER BY seat_id) AS grp
  FROM Cinema
  WHERE free = 1
)
SELECT COUNT(*) AS length
FROM free_seats
GROUP BY grp
HAVING COUNT(*) = (
  SELECT MAX(cnt) FROM (
    SELECT COUNT(*) AS cnt FROM free_seats GROUP BY grp
  ) t
);

1
2
3
4
5
6
7


def longest_consecutive_free_seats(cinema: 'pd.DataFrame') -> 'pd.DataFrame':
    df = cinema[cinema['free'] == 1].copy()
    df['grp'] = df['seat_id'] - range(len(df))
    group_sizes = df.groupby('grp').size()
    max_len = group_sizes.max() if not group_sizes.empty else 0
    result = group_sizes[group_sizes == max_len].reset_index(drop=True).to_frame('length')
    return result[['length']]

Complexity

⏰ Time complexity: O(n), where n is the number of seats. Each seat is processed once.
🧺 Space complexity: O(n), for storing group information and results.

Problem#

Example 1:#

Solution#

Method 1 – Window Functions and Grouping#

Intuition#

Approach#

Code#

Complexity#