LeetCode 603: Consecutive Available Seats

Problem Restatement

We are given a table called Cinema.

Each row tells us whether a seat is free or occupied.

We need to return all free seats that are part of at least one consecutive pair of free seats.

The result should be ordered by seat_id.

The problem note says seat_id is auto-incremented, free is a boolean, and consecutive available seats means at least two seats are consecutively available.

Input and Output

Input table:

Cinema

Output column:

seat_id

A seat should be returned if:

1. It is free.
2. The previous seat or next seat is also free.

Example

Input:

The free seats are:

Seat 1 is free, but seat 2 is occupied, so seat 1 is not part of a consecutive free pair.

Seats 3, 4, and 5 are consecutive and free.

Output:

First Thought: Compare Neighboring Rows

A seat belongs to the answer when it has at least one free neighbor.

For a seat a, a neighboring seat b satisfies:

ABS(a.seat_id - b.seat_id) = 1

So we can join the table with itself and compare each seat with its adjacent seats.

If both seats are free, then a.seat_id should be returned.

Key Insight

We do not need to find the whole block explicitly.

A seat is part of a consecutive available block of length at least 2 exactly when:

current seat is free
and
(previous seat is free or next seat is free)

For example, in the block:

3, 4, 5

Seat 3 has free next seat 4.

Seat 4 has free previous seat 3 and free next seat 5.

Seat 5 has free previous seat 4.

So all three seats are returned.

Algorithm

Use a self join.

Join Cinema as a with Cinema as b.

Keep only pairs where the seats are adjacent:

ABS(a.seat_id - b.seat_id) = 1

Then require both seats to be free:

a.free = 1 AND b.free = 1

Return a.seat_id.

Use DISTINCT because a middle seat may have two free neighbors and could appear twice.

Finally, order by seat_id.

SQL Solution

SELECT DISTINCT
    a.seat_id
FROM Cinema AS a
JOIN Cinema AS b
    ON ABS(a.seat_id - b.seat_id) = 1
WHERE a.free = 1
  AND b.free = 1
ORDER BY a.seat_id;

Code Explanation

The self join creates pairs of seats from the same table:

FROM Cinema AS a
JOIN Cinema AS b

The join condition keeps only adjacent seats:

ON ABS(a.seat_id - b.seat_id) = 1

This matches pairs such as:

Then the WHERE clause keeps only pairs where both seats are free:

WHERE a.free = 1
  AND b.free = 1

The query returns a.seat_id because we want every seat that participates in at least one valid adjacent pair.

We use:

SELECT DISTINCT

because a seat in the middle of a larger free block can match both the previous and next seats.

For example, seat 4 in the block 3, 4, 5 matches both 3 and 5.

Correctness

A seat returned by the query must satisfy two conditions.

First, a.free = 1, so the returned seat is free.

Second, the join found another row b such that ABS(a.seat_id - b.seat_id) = 1 and b.free = 1. Therefore, the returned seat has a free adjacent seat. So it belongs to a consecutive available pair.

Conversely, suppose a seat belongs to a consecutive available pair. Then it is free, and either the previous seat or the next seat is also free. The self join will match the current seat with that adjacent free seat. Therefore, the query will return it.

So the query returns exactly all consecutive available seats.

Complexity

Let n be the number of rows in Cinema.

With an index on seat_id, a database can optimize the adjacency lookup more efficiently.

Alternative: Window Function

We can also solve this by looking at the previous and next row.

WITH seats AS (
    SELECT
        seat_id,
        free,
        LAG(free) OVER (ORDER BY seat_id) AS prev_free,
        LEAD(free) OVER (ORDER BY seat_id) AS next_free
    FROM Cinema
)
SELECT
    seat_id
FROM seats
WHERE free = 1
  AND (
      prev_free = 1
      OR next_free = 1
  )
ORDER BY seat_id;

This version is often easier to read because it directly says:

“Return a free seat if the previous or next seat is also free.”

Testing

Sample data:

CREATE TABLE Cinema (
    seat_id INT,
    free BOOLEAN
);

INSERT INTO Cinema (seat_id, free) VALUES
    (1, 1),
    (2, 0),
    (3, 1),
    (4, 1),
    (5, 1);

Expected output:

Additional case:

TRUNCATE TABLE Cinema;

INSERT INTO Cinema (seat_id, free) VALUES
    (1, 1),
    (2, 1),
    (3, 0),
    (4, 1),
    (5, 0),
    (6, 1),
    (7, 1);

Expected output: