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
cinemawith at least two columns:seat_id(integer) andfree(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_idvalues 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
- Self-Join or Window Function: Use a self-join to compare each seat with its immediate neighbor.
- Filter Conditions: Ensure both seats in the pair are free.
- Select Seat IDs: Return the
seat_idof the first seat in each consecutive pair.
Algorithm Steps:
- Perform a self-join on the
cinematable, 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). - Add a filter to ensure both seats are free (
T1.free = True AND T2.free = True). - Select the
seat_idfrom the first table in the join result.
Complexity Analysis
- Time Complexity: O(n), where n is the number of rows in the
cinematable. 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_idvalues are sequential but handles any order by using the join condition.