Skip to content

603. Consecutive Available Seats πŸ”’

Description

Table: Cinema

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

 

Find all the consecutive available seats in the cinema.

Return the result table ordered by seat_id in ascending order.

The test cases are generated so that more than two seats are consecutively available.

The result format is in the following example.

 

Example 1:

Input: 
Cinema table:
+---------+------+
| seat_id | free |
+---------+------+
| 1       | 1    |
| 2       | 0    |
| 3       | 1    |
| 4       | 1    |
| 5       | 1    |
+---------+------+
Output: 
+---------+
| seat_id |
+---------+
| 3       |
| 4       |
| 5       |
+---------+

Solutions

Solution 1: Self-Join

Thinking

A free seat counts only if it has a neighboring free seat. A correlated lookup of neighbors repeats the same probes.

Self-join seats whose ids differ by \(1\) and are both free; distinct ids in that join are the answer.

We can use a self-join to join the Seat table with itself, and then filter out the records where the id of the left seat is equal to the id of the right seat minus \(1\), and where both seats are empty.

1
2
3
4
5
6
# Write your MySQL query statement below
SELECT DISTINCT a.seat_id
FROM
    Cinema AS a
    JOIN Cinema AS b ON ABS(a.seat_id - b.seat_id) = 1 AND a.free AND b.free
ORDER BY 1;

Solution 2: Window Function

Thinking

The self-join materializes pairs. LAG/LEAD read the neighboring free flags on the same row; if the seat plus either neighbor sums to \(2\), it belongs to a consecutive free pair.

We can use the LAG and LEAD functions (or SUM() OVER(ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING)) to obtain the information of adjacent seats, and then filter out the consecutive empty seats and sort them in a unique way.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
# Write your MySQL query statement below
WITH
    T AS (
        SELECT
            seat_id,
            (free + (LAG(free) OVER (ORDER BY seat_id))) AS a,
            (free + (LEAD(free) OVER (ORDER BY seat_id))) AS b
        FROM Cinema
    )
SELECT seat_id
FROM T
WHERE a = 2 OR b = 2;

Solution 3

Thinking

A single sliding SUM(free) over the previous, current, and next rows replaces separate LAG/LEAD. A free seat with window sum greater than \(1\) has at least one free neighbor.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
# Write your MySQL query statement below
WITH
    T AS (
        SELECT
            *,
            SUM(free = 1) OVER (
                ORDER BY seat_id
                ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING
            ) AS cnt
        FROM Cinema
    )
SELECT seat_id
FROM T
WHERE free = 1 AND cnt > 1
ORDER BY 1;

Comments