Domain 1EasyCORE

Consecutive Available Seats

The problem asks us to find consecutive available seats in a cinema database. Given a table `cinema` with columns `seat_id` (an integer representing the seat number) and `free` (a boolean indicating whether the seat is free), we need to return the seat IDs of all pairs of consecutive free seats.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#**FAANG asked:** 1

603. Consecutive Available Seats

Model: qwen2.5-coder:14b
Topics:
FAANG asked: 1
Acceptance rate: 66.3%


Problem Breakdown

The problem asks us to find consecutive available seats in a cinema database. Given a table cinema with columns seat_id (an integer representing the seat number) and free (a boolean indicating whether the seat is free), we need to return the seat IDs of all pairs of consecutive free seats.

Inputs:

  • A table cinema with at least two columns: seat_id (integer) and free (boolean).

Outputs:

  • A list of seat IDs where each pair represents two consecutive free seats.

Implicit Constraints or Tricky Edge Cases:

  • The table might be empty.
  • There could be no consecutive free seats.
  • The seat_id values are not necessarily sequential but should be considered in ascending order.
  • The solution should handle large datasets efficiently.

Intuition

A brute-force approach would involve checking each seat and its immediate neighbor to see if both are free. This approach is inefficient because it requires sorting the data first, which could lead to a time complexity of O(n log n) due to sorting, followed by a linear scan, resulting in an overall complexity of O(n log n).

A better approach involves using self-joins or window functions to efficiently find consecutive free seats without needing to sort the entire table. The key insight is that we can join the cinema table with itself on the condition that one seat’s ID is exactly one more than another’s, and both are marked as free.

Approach

  1. Self-Join or Window Function: Use a self-join to compare each seat with its immediate neighbor.
  2. Filter Conditions: Ensure both seats in the pair are free.
  3. Select Seat IDs: Return the seat_id of the first seat in each consecutive pair.

Algorithm Steps:

  1. Perform a self-join on the cinema table, joining it with itself on the condition that one seat’s ID is exactly one more than another’s (T1.seat_id = T2.seat_id + 1).
  2. Add a filter to ensure both seats are free (T1.free = True AND T2.free = True).
  3. Select the seat_id from the first table in the join result.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of rows in the cinema table. This is because we perform a single pass through the data with a self-join.
  • Space Complexity: O(1) for the query itself, assuming the database handles memory efficiently.

Solution

SELECT T1.seat_id 
FROM cinema AS T1 
JOIN cinema AS T2 ON T1.seat_id = T2.seat_id + 1 
WHERE T1.free = True AND T2.free = True;

Edge Cases Handled

  • Empty Table: The query will return an empty result set if the table is empty.
  • No Consecutive Free Seats: If there are no consecutive free seats, the query will also return an empty result set.
  • Single Seat: If there’s only one seat in the table, it cannot form a pair, so the query will return nothing.
  • Sequential IDs: The solution assumes seat_id values are sequential but handles any order by using the join condition.