Leetcode MEDIUM 3140 - Consecutive Available Seats II RANKING SQL - Solved by Everyday Data Science
Consecutive Available Seats II - Video Solution
Watch 2 video solutions for Consecutive Available Seats II, a medium level problem involving Database. This walkthrough by Everyday Data Science has 1,009 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Window Function with ROW_NUMBER grouping | O(n) | O(n) | Best general solution for detecting consecutive sequences in ordered data |
| Window Function with LAG and cumulative grouping | O(n) | O(n) | Useful when identifying breaks between rows or computing streaks |
| Self-Join or Correlated Subquery | O(n^2) | O(1) | Works on databases without window function support but scales poorly |