Is Consecutive Available Seats easy or hard?

Consecutive Available Seats is classified as an Easy SQL problem. The logic relies on identifying adjacent seat IDs with the same availability status. Candidates familiar with SQL joins or window functions can typically solve it quickly during interviews.

Consecutive Available Seats Python/Java solution

This problem is primarily solved using SQL because the dataset is stored in a database table. In practice platforms like MySQL or PostgreSQL are used with queries involving self joins or window functions. Python or Java solutions would typically interact with the database and execute the SQL query rather than reimplementing the logic in code.

How to solve Consecutive Available Seats in O(n)?

Scan the table ordered by seat_id and compare each row with its neighbors. Using SQL window functions like LAG() and LEAD(), check if the current seat is free and whether the previous or next seat is also free. If either condition holds, return the seat_id. This performs a single pass over the table, resulting in O(n) complexity.

What is the best approach for Consecutive Available Seats?

The self-join approach is the most common solution. It joins the cinema table with itself and checks whether two rows have consecutive seat_id values and both are marked free. This runs in O(n) time and uses constant extra space. Window functions such as LAG and LEAD offer a cleaner alternative in modern SQL databases.

Is Consecutive Available Seats asked at Google/Amazon/Meta?

Database querying problems similar to Consecutive Available Seats appear in SQL interview rounds at companies such as Amazon, Meta, and other data-driven teams. The question tests understanding of joins, row comparisons, and window functions rather than complex algorithms.

What data structure is used in Consecutive Available Seats?

The problem operates on a relational table rather than traditional data structures like arrays or hash maps. The key concept is comparing rows using SQL joins or window functions. These techniques allow efficient detection of consecutive seat_id values.

What is the time complexity of Consecutive Available Seats?

Most efficient SQL solutions run in O(n) time where n is the number of rows in the cinema table. The query scans rows once and compares adjacent seat IDs using joins or window functions. Since no additional data structures are required, the space complexity remains O(1).

Description Solution Video 17:51

603. Consecutive Available Seats

Easy64.9% acceptancePremium elsewhere, free here

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 i^th seat is free or not. 1 means free while 0 means occupied.

Find all the consecutive available seats in the cinema.

Return the result table ordered by seat_id in ascending order.

The test cases are generated so that more than two seats are consecutively available.

The result format is in the following example.

Example 1:

Input: 
Cinema table:
+---------+------+
| seat_id | free |
+---------+------+
| 1       | 1    |
| 2       | 0    |
| 3       | 1    |
| 4       | 1    |
| 5       | 1    |
+---------+------+
Output: 
+---------+
| seat_id |
+---------+
| 3       |
| 4       |
| 5       |
+---------+

Topics

Database

17:51

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1

Input

{"headers":{"Cinema":["seat_id","free"]},"rows":{"Cinema":[[1,1],[2,0],[3,1],[4,1],[5,1]]}}

Your code is saved on this device.Solution