Skip to main content
Talentd

Consecutive Available Seats - Solution & Explanation

EasyPremiumFree on FleetCodeDatabase4 min read
Practice this problem

Problem Statement

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

Approach Overview

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 1: Self-Join

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.

Code

MySQL

MySQL

Try this approach in the editor →

Approach 2: Window Function

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.

Code

MySQL

MySQL

Try this approach in the editor →

Approach 3: Default Approach

Code

MySQL

MySQL

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Self-Join—
Window Function—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Self-JoinO(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 CheckO(n)O(1)Simple logic when directly checking adjacent IDs

Video Solution

LeetCode Interview SQL Question with Detailed Explanation | Practice SQL | LeetCode 603 | Window Fun • Everyday Data Science • 31,214 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Consecutive Available Seats easy or hard?
Consecutive Available Seats is classified as an Easy SQL problem. The logic relies on identifying adjacent seat IDs with the same availability status. Candidates familiar with SQL joins or window functions can typically solve it quickly during interviews.
Consecutive Available Seats Python/Java solution
This problem is primarily solved using SQL because the dataset is stored in a database table. In practice platforms like MySQL or PostgreSQL are used with queries involving self joins or window functions. Python or Java solutions would typically interact with the database and execute the SQL query rather than reimplementing the logic in code.
How to solve Consecutive Available Seats in O(n)?
Scan the table ordered by seat_id and compare each row with its neighbors. Using SQL window functions like LAG() and LEAD(), check if the current seat is free and whether the previous or next seat is also free. If either condition holds, return the seat_id. This performs a single pass over the table, resulting in O(n) complexity.
What is the best approach for Consecutive Available Seats?
The self-join approach is the most common solution. It joins the cinema table with itself and checks whether two rows have consecutive seat_id values and both are marked free. This runs in O(n) time and uses constant extra space. Window functions such as LAG and LEAD offer a cleaner alternative in modern SQL databases.
Is Consecutive Available Seats asked at Google/Amazon/Meta?
Database querying problems similar to Consecutive Available Seats appear in SQL interview rounds at companies such as Amazon, Meta, and other data-driven teams. The question tests understanding of joins, row comparisons, and window functions rather than complex algorithms.
What data structure is used in Consecutive Available Seats?
The problem operates on a relational table rather than traditional data structures like arrays or hash maps. The key concept is comparing rows using SQL joins or window functions. These techniques allow efficient detection of consecutive seat_id values.
What is the time complexity of Consecutive Available Seats?
Most efficient SQL solutions run in O(n) time where n is the number of rows in the cinema table. The query scans rows once and compares adjacent seat IDs using joins or window functions. Since no additional data structures are required, the space complexity remains O(1).

Ready to solve this problem?

Practice Consecutive Available Seats with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary