How to Find Consecutive Empty Seats Using SQL Window Functions ?

byknowstar •

 Finding consecutive empty seats in a booking system, like a cinema hall, is a common challenge asked in SQL interviews and online coding platforms such as Leetcode. The task is to identify a sequence of n empty seats so a group can book them together. This problem involves checking seat availability and their order, then detecting groups of empty seats appearing consecutively.

To solve this, we'll explore an approach using SQL window functions which makes it efficient and straightforward. We'll walk through the logic using a sample table, step-by-step SQL code, and tips for adjusting the solution to work with any number of consecutive seats.

Understanding the Problem: Finding Consecutive Empty Seats in SQL

Imagine you have a table called seating that tracks seats in a theater. Each seat has an ID representing its position and a status showing if it is free or occupied. Here’s what the table looks like:

seat_id free
1 n
2 y
3 y
4 n
5 y
6 n
7 n
8 y
9 y
10 y

CREATE TABLE [dbo].[Seating](
[SeatID] [int] NULL,
 [Free] [char](1) NULL
) 
GO
INSERT [dbo].[Seating] ([SeatID], [Free]) VALUES 
(1, 'Y'),
(2, 'N'),
(3, 'N'),
(4, 'Y'),
(5, 'Y'),
(6, 'N'),
(7, 'Y'),
(8, 'Y'),
(9, 'Y'),
(10, 'Y')

The seat_id column shows the order of the seats. The free column shows if the seat is empty (y) or occupied (n).

The goal is to find where there are n consecutive seats marked as free. For example, if you want to find 3 consecutive empty seats, the query should point out seats 8, 9, and 10.

There are various ways to solve this problem in SQL, but using window functions offers a cleaner and scalable solution. Window functions allow us to perform calculations across rows relative to the current one, which is perfect for checking adjacent seat statuses.

Step 1: Identifying Empty Seats with a CASE Statement

The first step is to mark which seats are empty so we can calculate consecutive empty seats easier.

We can create a simple CASE statement that assigns a value of 1 to an empty seat (free = 'y') and 0 otherwise. This converts the seat availability into numeric form, which we can then sum over groups of seats.

Here is an example SQL snippet for that:

SELECT 
  seat_id,
  free,
  CASE WHEN free = 'y' THEN 1 ELSE 0 END AS is_empty
FROM seating;

Summary of the logic:

  • If the seat is free (y), assign 1.
  • If the seat is occupied (n), assign 0.

This numeric flag is valuable because it lets us sum over a range of seats and identify if all seats in that range are empty.

Step 2: Logic Behind Finding Consecutive Empty Seats

To find a block of consecutive empty seats, we need to check not only the current seat but also its neighbors. For example, for 3 consecutive seats, each seat is part of a group including 1 preceding seat and 1 following seat.

Here’s the logic broken down with an example:

  • Look at seat number 9, which is empty.
  • Check the previous seat, number 8, also empty.
  • Check the next seat, number 10, also empty.

If all three are empty, that means seats 8, 9, and 10 form 3 consecutive empty seats.

We can implement this by summing the is_empty values over a window frame that covers these three seats. If the sum equals 3, all seats in that window are empty.

To do this, use the window function with the OVER clause and specify the window frame using ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING.

Example query:

SELECT
  seat_id,
  free,
  CASE WHEN free = 'y' THEN 1 ELSE 0 END AS is_empty,
  SUM(CASE WHEN free = 'y' THEN 1 ELSE 0 END) 
    OVER (ORDER BY seat_id ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING) AS consecutive_empty_seats
FROM seating;

Here’s how it works step-by-step:

  1. For each seat_id, compute is_empty as 1 or 0.
  2. Define a window frame that includes the current row, one row before, and one row after.
  3. Sum the is_empty values within this frame.
  4. If the sum is 3, it means there are 3 consecutive empty seats including the current one.

This window frame approach allows us to slide over the seat list and detect consecutive empty seats without complicated self-joins or cursors.

Step 3: Making the Query Dynamic for Any Number of Consecutive Seats

Sometimes, you want to find not just 3 but n consecutive empty seats. The key is adapting your window frame to cover exactly n seats for counting.

For instance, to find 4 consecutive empty seats:

  1. If we update seat 7 to be empty ('y'), seats 7, 8, 9, and 10 form 4 empty seats.
  2. Adjust the window frame to include 4 rows in total.

You can set your frame as:

  • ROWS BETWEEN 2 PRECEDING AND 1 FOLLOWING
    (current seat plus 2 before and 1 after = 4 seats), or
  • ROWS BETWEEN 1 PRECEDING AND 2 FOLLOWING

Both these options cover 4 rows, just shifting the frame before or after the current seat.

Here’s an example updating seat 7 and adjusting the window:

UPDATE seating SET free = 'y' WHERE seat_id = 7;

SELECT
  seat_id,
  free,
  CASE WHEN free = 'y' THEN 1 ELSE 0 END AS is_empty,
  SUM(CASE WHEN free = 'y' THEN 1 ELSE 0 END)
    OVER (ORDER BY seat_id ROWS BETWEEN 2 PRECEDING AND 1 FOLLOWING) AS consecutive_empty_seats
FROM seating;

It’s important to:

  • Ensure your window frame includes exactly n seats.
  • Always count the current seat plus appropriate preceding and following seats.

This makes the query flexible to find any group size.

Number of Seats (n) Window Frame Example
3 ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING
4 ROWS BETWEEN 2 PRECEDING AND 1 FOLLOWING or ROWS BETWEEN 1 PRECEDING AND 2 FOLLOWING
n ROWS BETWEEN (n-2) PRECEDING AND 1 FOLLOWING or similar arrangement

Step 4: Wrapping Logic in a CTE or Subquery for Filtering Results

To cleanly extract only those rows where you have n consecutive free seats, wrap the previous logic inside a Common Table Expression (CTE) or a subquery.

This makes the query easier to read and maintain.

Example using a CTE:

WITH empty_seats_cte AS (
  SELECT
    seat_id,
    free,
    CASE WHEN free = 'y' THEN 1 ELSE 0 END AS is_empty,
    SUM(CASE WHEN free = 'y' THEN 1 ELSE 0 END)
      OVER (ORDER BY seat_id ROWS BETWEEN 2 PRECEDING AND 1 FOLLOWING) AS consecutive_empty_seats
  FROM seating
)
SELECT seat_id
FROM empty_seats_cte
WHERE consecutive_empty_seats = 4;

This query returns the central seat ID for each block of 4 consecutive empty seats.

A benefit of using a CTE:

  • Keeps the window function logic separate from filtering
  • Helps structure larger queries with multiple steps
  • Increases readability and debugging ease

Step 5: Extracting All Seat IDs in the Consecutive Group Using LAG and LEAD

Often, you want to get all the seat IDs forming the consecutive group, not just the middle seat. SQL lets you do this by using the LAG() and LEAD() functions.

What these functions do:

  • LAG(seat_id, offset) gets the seat ID offset rows before the current row
  • LEAD(seat_id, offset) gets the seat ID offset rows after the current row

If you want to list four consecutive seats, you combine:

  1. LAG(seat_id, 2) → seat 1 (two seats before current)
  2. LAG(seat_id, 1) → seat 2 (one seat before current)
  3. seat_id → seat 3 (current seat)
  4. LEAD(seat_id, 1) → seat 4 (one seat after current)

Example query to select all 4 seat IDs in a consecutive block:

WITH empty_seats_cte AS (
  SELECT
    seat_id,
    free,
    CASE WHEN free = 'y' THEN 1 ELSE 0 END AS is_empty,
    SUM(CASE WHEN free = 'y' THEN 1 ELSE 0 END)
      OVER (ORDER BY seat_id ROWS BETWEEN 2 PRECEDING AND 1 FOLLOWING) AS consecutive_empty_seats
  FROM seating
)
SELECT
  LAG(seat_id, 2) OVER (ORDER BY seat_id) AS seat1,
  LAG(seat_id, 1) OVER (ORDER BY seat_id) AS seat2,
  seat_id AS seat3,
  LEAD(seat_id, 1) OVER (ORDER BY seat_id) AS seat4
FROM empty_seats_cte
WHERE consecutive_empty_seats = 4;

This returns rows with columns showing the IDs of all four adjacent empty seats.

Steps explained:

  1. Identify rows with 4 consecutive empty seats.
  2. Use window functions LAG and LEAD with proper offsets to get surrounding seat IDs.
  3. Select these seat IDs in separate columns for clarity.

This method allows you to present the exact seats available for booking as a group.

Additional Tips and Resources

Window functions are incredibly useful for tasks that require comparing rows relative to each other, like this consecutive seats problem.

To get better at SQL interview questions, practice similar pattern problems involving ranking, grouping, and running totals. The more you work with window functions, the more intuitive this logic becomes.

If you want more tutorials on SQL and advanced queries like this, consider checking out Learn at Knowstar’s YouTube channel. They cover numerous SQL topics with clean explanations.

For those interested, the creator also shares data analytics certification recommendations and tech gear for software professionals in the video description here. You can explore those options if you want to improve your skills or work setup.

Finding consecutive empty seats in SQL is entirely doable with a combination of CASE, window functions, and simple logic. Following this approach, you can handle dynamic seat blocks efficiently and write clean queries that pass interview tests with ease.

Happy querying!

https://www.youtube.com/watch?v=e21QTdfLyFY


Post a Comment

Previous Post Next Post
Share to other apps
Copy Post Link

Contact Form