Skip to main content
Talentd

Consecutive Available Seats II - Solution & Explanation

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

Write a solution to find the length of longest consecutive sequence of available seats in the cinema.

Note:

  • There will always be at most one longest consecutive sequence.
  • If there are multiple consecutive sequences with the same length, include all of them in the output.

Return the result table ordered by first_seat_id in ascending order.

The result format is in the following example.

 

Example:

Input:

Cinema table:

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

Output:

+-----------------+----------------+-----------------------+
| first_seat_id   | last_seat_id   | consecutive_seats_len |
+-----------------+----------------+-----------------------+
| 3               | 5              | 3                     |
+-----------------+----------------+-----------------------+

Explanation:

  • Longest consecutive sequence of available seats starts from seat 3 and ends at seat 5 with a length of 3.
Output table is ordered by first_seat_id in ascending order.

Approach Overview

Problem Overview: You are given a table of seats where each row indicates whether a seat is available. The goal is to identify blocks of consecutive available seats. Instead of checking seats one by one with nested queries, the efficient solution uses SQL window functions to detect consecutive sequences.

Approach 1: Window Function with Row Number (O(n) time, O(n) space)

The key idea is that consecutive values share a consistent difference between the seat identifier and a generated row index. First filter rows where the seat is available. Then compute ROW_NUMBER() OVER (ORDER BY seat_id). For consecutive seats, the value seat_id - row_number remains constant. This creates a grouping key that identifies each contiguous block. Once grouped, aggregate using MIN(seat_id), MAX(seat_id), and COUNT(*) to determine the start, end, and length of each available sequence. The query scans the table once and uses a window function plus grouping, giving O(n) time complexity with O(n) intermediate storage.

Another variation uses LAG() to compare the current seat with the previous seat ordered by seat_id. When the difference between adjacent available seats is greater than 1, a new block begins. A cumulative sum over these breakpoints forms a group identifier for each consecutive segment. This pattern is common when solving SQL problems involving sequences, gaps, or streak detection.

This approach is preferred when working with modern SQL engines such as MySQL 8+, PostgreSQL, or SQL Server that support window functions. It avoids self-joins and correlated subqueries, keeping the query readable and efficient even for large seat tables.

Conceptually, the problem is a classic gaps and islands pattern in SQL. Window functions allow you to convert row order information into grouping logic. If you want to explore related techniques, review problems under Database, SQL, and Window Functions.

Recommended for interviews: The window function approach using ROW_NUMBER() or LAG() is the expected solution. It demonstrates that you understand sequence grouping in SQL. Simpler scans show the basic idea, but window functions show strong SQL problem‑solving ability.

Solution

First, we find all the vacant seats, and then group the seats. The grouping is based on the seat number minus its ranking. In this way, consecutive vacant seats will be grouped together. Then we find the minimum seat number, maximum seat number, and length of consecutive seats in each group. Finally, we find the group with the longest length of consecutive seats, and output the minimum seat number, maximum seat number, and length of consecutive seats in this group.

Code

MySQL

MySQL

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Window Function with ROW_NUMBER groupingO(n)O(n)Best general solution for detecting consecutive sequences in ordered data
Window Function with LAG and cumulative groupingO(n)O(n)Useful when identifying breaks between rows or computing streaks
Self-Join or Correlated SubqueryO(n^2)O(1)Works on databases without window function support but scales poorly

Video Solution

Leetcode MEDIUM 3140 - Consecutive Available Seats II RANKING SQL - Solved by Everyday Data Science • Everyday Data Science • 1,009 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Consecutive Available Seats II easy or hard?
Consecutive Available Seats II is considered a Medium difficulty database problem. The challenge lies in recognizing the gaps-and-islands pattern and using window functions correctly to group consecutive rows.
Consecutive Available Seats II Python/Java solution
This problem is designed for SQL rather than Python or Java. The correct solution uses database queries with window functions like ROW_NUMBER() or LAG() to detect consecutive available seats efficiently.
How to solve Consecutive Available Seats II in O(n)?
Filter available seats, compute ROW_NUMBER() ordered by seat_id, and subtract it from seat_id to create a stable grouping key. Seats that are consecutive produce the same key. Group by this value and aggregate to find each block of consecutive seats. The query processes rows once, giving O(n) performance.
What is the best approach for Consecutive Available Seats II?
The best approach uses SQL window functions such as ROW_NUMBER() or LAG(). By ordering seats and generating row numbers, you can detect consecutive sequences using the difference between seat_id and row_number. This converts the problem into a grouping operation and runs in O(n) time with a single table scan.
Is Consecutive Available Seats II asked at Google/Amazon/Meta?
Database sequence problems similar to Consecutive Available Seats II appear in SQL interviews at companies like Amazon, Meta, and Google. Interviewers often test the gaps-and-islands pattern using window functions such as ROW_NUMBER(), LAG(), or LEAD().
What data structure is used in Consecutive Available Seats II?
The problem relies on SQL window functions rather than traditional data structures. Ordering rows by seat_id and computing ROW_NUMBER() or LAG() effectively creates positional metadata that helps identify consecutive sequences.
What is the time complexity of Consecutive Available Seats II?
The optimal window function solution runs in O(n) time because the database scans the table once and computes window values per row. Grouping the sequences also operates in linear time. Space complexity is typically O(n) due to intermediate window function results.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary