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

| Column | Type | Meaning |
|---|---|---|
| `seat_id` | int | Seat id |
| `free` | bool | `1` means free, `0` means 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:

```sql
Cinema
```

Output column:

```sql
seat_id
```

A seat should be returned if:

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

## Example

Input:

| seat_id | free |
|---:|---:|
| 1 | 1 |
| 2 | 0 |
| 3 | 1 |
| 4 | 1 |
| 5 | 1 |

The free seats are:

| seat_id | free |
|---:|---:|
| 1 | 1 |
| 3 | 1 |
| 4 | 1 |
| 5 | 1 |

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:

| seat_id |
|---:|
| 3 |
| 4 |
| 5 |

## 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:

```sql
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:

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

For example, in the block:

```text
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:

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

Then require both seats to be free:

```sql
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

```sql
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:

```sql
FROM Cinema AS a
JOIN Cinema AS b
```

The join condition keeps only adjacent seats:

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

This matches pairs such as:

| `a.seat_id` | `b.seat_id` |
|---:|---:|
| 3 | 4 |
| 4 | 3 |
| 4 | 5 |
| 5 | 4 |

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

```sql
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:

```sql
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`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^2)` worst case | A self join can compare many row pairs |
| Space | `O(n)` | The result and join processing may store matching rows |

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.

```sql
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:

```sql
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:

| seat_id |
|---:|
| 3 |
| 4 |
| 5 |

Additional case:

```sql
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:

| seat_id |
|---:|
| 1 |
| 2 |
| 6 |
| 7 |