Consecutive Available Seats II - Solution & Explanation

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.