Watch 8 video solutions for Consecutive Available Seats, a easy level problem involving Database. This walkthrough by Everyday Data Science has 29,557 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 | +---------+
Problem Overview: The Consecutive Available Seats problem asks you to return all seat IDs in a cinema where the seat is free and at least one adjacent seat (previous or next seat ID) is also free. The input table typically contains seat_id and free. You must identify seats that form part of a consecutive pair of available seats.
Approach 1: Self-Join (O(n) time, O(1) extra space)
This method joins the cinema table with itself to compare neighboring seat IDs. The key idea is that two seats are consecutive when ABS(a.seat_id - b.seat_id) = 1. During the join, you filter rows where both seats are marked as available (free = 1). The result returns seat IDs that participate in at least one valid pair. This approach works well because SQL joins naturally compare rows within the same dataset and efficiently detect adjacency relationships.
Approach 2: Window Function (O(n) time, O(1) extra space)
Window functions make this query cleaner by comparing each row with its neighbors directly. Using LAG() and LEAD(), you can check whether the previous or next seat is free while scanning the table once ordered by seat_id. If the current seat is free and either adjacent seat is also free, include it in the result. This approach avoids explicit joins and expresses the logic more clearly. In databases that support analytic functions, this is usually the most readable and maintainable solution.
Approach 3: Conditional Neighbor Check (O(n) time, O(1) space)
A simpler SQL strategy checks neighboring rows using conditional comparisons. You filter seats where free = 1 and either seat_id + 1 or seat_id - 1 corresponds to another available seat. This can be implemented with subqueries or conditional joins. The logic directly models the requirement: a seat qualifies if it forms a consecutive pair with another free seat.
All solutions rely on the same insight: the problem reduces to detecting adjacent IDs with the same availability state. Because the table is typically small and indexed by seat_id, each query effectively runs in linear time relative to the number of rows.
Recommended for interviews: The Self-Join solution is the most commonly expected answer because it demonstrates strong understanding of relational operations and row comparisons. The Window Function approach shows deeper SQL knowledge and often produces cleaner queries in modern databases. If the interviewer focuses on traditional SQL fundamentals, start with the self-join. Then mention window functions as a more expressive alternative.
This problem is a good exercise in SQL query design, especially row comparison patterns using joins and analytic techniques like window functions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Self-Join | O(n) | O(1) | Standard SQL approach when window functions are unavailable |
| Window Function (LAG/LEAD) | O(n) | O(1) | Cleaner solution when the database supports analytic functions |
| Conditional Neighbor Check | O(n) | O(1) | Simple logic when directly checking adjacent IDs |
