LeetCode 603 - Consecutive Available Seats

LeetCode Problem 603

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

The problem gives us a database table named Cinema with two columns:

Column	Meaning
seat_id	Unique identifier for a seat
free	Whether the seat is available, where 1 means free and 0 means occupied

We need to find all seats that are part of at least one consecutive sequence of free seats. Two seats are consecutive if their seat_id values differ by exactly 1.

The important detail is that we are not just looking for pairs. If a longer sequence exists, every seat in that sequence should be returned. For example, if seats 3, 4, and 5 are all free, then all three seats belong to a consecutive available block and all should appear in the output.

The result must contain only the seat_id column, and the rows must be ordered in ascending order of seat_id.

The input table represents the current occupancy state of a cinema. Every row corresponds to exactly one seat. Since seat_id is auto incremented, seat numbers increase sequentially, which allows us to detect adjacency using simple arithmetic comparisons such as seat_id + 1.

One important guarantee in the problem statement is that the test cases include sequences longer than two seats. This means the solution must correctly identify all seats participating in any consecutive free segment, not just isolated pairs.

Several edge cases are important to consider. A free seat by itself should not be included because it is not consecutive with another free seat. Consecutive sequences can appear at the beginning or end of the table, so boundary handling matters. Another subtle case occurs when a seat belongs to multiple adjacent pairs. For example, in the sequence 3, 4, 5, seat 4 is consecutive with both 3 and 5, but it should still appear only once in the output.

Approaches

Brute Force Approach

A straightforward approach is to examine every seat individually and check its neighboring seats. For each free seat, we can search for a seat with seat_id - 1 and another with seat_id + 1. If either neighboring seat is also free, then the current seat belongs to a consecutive free block.

This approach is correct because a seat is considered valid if at least one adjacent seat is also free. By explicitly checking both neighbors for every seat, we guarantee that all qualifying seats are detected.

However, a naive implementation can become inefficient if each neighbor lookup requires scanning the entire table. In that case, for every row we may perform another full traversal, leading to quadratic time complexity.

Optimal Approach

The key observation is that consecutive seats differ by exactly 1 in their seat_id values. Instead of repeatedly scanning the table, we can use a self join.

We join the Cinema table with itself such that one seat is adjacent to another:

• c1.seat_id = c2.seat_id + 1
• or c1.seat_id = c2.seat_id - 1

We also require both seats to be free.

If a seat has at least one neighboring free seat, then it belongs to a consecutive available sequence and should be returned.

This approach works efficiently because relational databases are optimized for joins and indexed comparisons.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Repeatedly scans the table for neighboring seats
Optimal	O(n log n) typically	O(1) extra	Uses a self join to efficiently detect adjacent free seats

Algorithm Walkthrough

1. Start with the Cinema table and consider each seat as a candidate result.
2. Create a self join between the table and itself. One copy represents the current seat, and the other represents a potential neighboring seat.
3. Define adjacency using seat identifiers. Two seats are consecutive if one seat's seat_id differs from the other by exactly 1.
4. Restrict the comparison to free seats only. Both seats in the pair must have free = 1.
5. If a seat has at least one adjacent free seat, include it in the result set. This ensures that every seat participating in a consecutive block is returned.
6. Use DISTINCT to avoid duplicates. A seat in the middle of a longer sequence may match multiple neighboring seats, and we only want to return it once.
7. Sort the final result by seat_id in ascending order to satisfy the output requirement.

Why it works

The core invariant is that every valid seat must have at least one neighboring seat whose seat_id differs by exactly 1 and is also free. The self join explicitly checks this condition for every seat. Any seat satisfying the condition is guaranteed to belong to a consecutive free sequence, and any seat that does not satisfy it cannot belong to such a sequence. Therefore, the algorithm returns exactly the correct seats.

Python Solution

# Write your MySQL query statement below

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

The query begins by creating two aliases of the same table, c1 and c2. This allows us to compare seats against other seats in the table.

The join condition uses ABS(c1.seat_id - c2.seat_id) = 1, which ensures the two seats are adjacent. Using ABS simplifies the logic because it handles both left and right neighbors in a single expression.

The WHERE clause guarantees that both seats are free. If either seat is occupied, the pair is ignored.

Because a seat may match more than one adjacent seat, DISTINCT removes duplicate entries. Finally, the query orders the result by seat_id in ascending order.

Go Solution

// Write your MySQL query statement below

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

Unlike algorithmic problems implemented in Go, this database problem requires only an SQL query submission on LeetCode. Therefore, the same SQL solution is used regardless of programming language selection.

There are no Go-specific concerns such as slices, maps, integer overflow, or memory allocation because the execution is entirely handled by the SQL engine.

Worked Examples

Example 1

Input table:

seat_id	free
1	1
2	0
3	1
4	1
5	1

We compare each free seat against adjacent seats.

c1.seat_id	c2.seat_id	Adjacent?	Both Free?	Included?
1	2	Yes	No	No
3	4	Yes	Yes	Yes
4	3	Yes	Yes	Yes
4	5	Yes	Yes	Yes
5	4	Yes	Yes	Yes

After removing duplicates with DISTINCT, the final result becomes:

| seat_id |

|---|---|

| 3 |

| 4 |

| 5 |

Seat 1 is excluded because its only adjacent seat, 2, is occupied.

Seats 3, 4, and 5 are all included because each has at least one neighboring free seat.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n) typically	The database performs a self join and sorting
Space	O(1) extra	No additional data structures are explicitly created

The dominant operation is the self join. In practice, database engines optimize joins using indexes and execution plans, so performance is typically much better than a naive quadratic scan. The query itself does not allocate extra application level memory beyond the database execution structures.

Test Cases

# Example case with a consecutive block
assert query([[1,1],[2,0],[3,1],[4,1],[5,1]]) == [3,4,5]

# Two consecutive free seats
assert query([[1,1],[2,1]]) == [1,2]

# No consecutive free seats
assert query([[1,1],[2,0],[3,1],[4,0]]) == []

# Consecutive sequence at the beginning
assert query([[1,1],[2,1],[3,0]]) == [1,2]

# Consecutive sequence at the end
assert query([[1,0],[2,1],[3,1]]) == [2,3]

# Long consecutive block
assert query([[1,1],[2,1],[3,1],[4,1]]) == [1,2,3,4]

# Occupied seats only
assert query([[1,0],[2,0],[3,0]]) == []

# Multiple separate consecutive groups
assert query([[1,1],[2,1],[3,0],[4,1],[5,1]]) == [1,2,4,5]

# Single free seat only
assert query([[1,1]]) == []

Test	Why
Example input	Validates the standard scenario
Two consecutive seats	Smallest valid consecutive block
No consecutive seats	Ensures isolated free seats are excluded
Consecutive block at beginning	Tests lower boundary handling
Consecutive block at end	Tests upper boundary handling
Long consecutive block	Ensures all seats in the sequence are returned
All occupied	Ensures empty result handling
Multiple groups	Verifies separate consecutive ranges
Single seat	Ensures isolated seat is ignored

Edge Cases

One important edge case is an isolated free seat. For example, if seat 3 is free but seats 2 and 4 are occupied, then seat 3 must not appear in the output. A buggy implementation might incorrectly include all free seats without verifying adjacency. The self join prevents this because a seat only appears if it matches another free seat with a difference of exactly 1.

Another important case is a long consecutive sequence such as 1, 2, 3, 4, 5. Seats in the middle participate in multiple adjacent pairs. For example, seat 3 matches both 2 and 4. Without DISTINCT, duplicate rows would appear in the result. The implementation handles this correctly by explicitly removing duplicates.

Boundary positions are also significant. A seat at the beginning or end of the numbering range has only one possible neighbor. For example, seat 1 can only match seat 2. Some implementations incorrectly assume both neighbors exist. The self join approach naturally handles missing neighbors because only valid matching rows participate in the join.

A final subtle edge case occurs when all seats are occupied or when the table contains only one row. In these cases, no valid adjacent free pairs exist, so the query correctly returns an empty result set.