Flight Occupancy and Waitlist Analysis - Solution & Explanation

Q: Is Flight Occupancy and Waitlist Analysis easy or hard?

Flight Occupancy and Waitlist Analysis is considered a medium difficulty database problem. The challenge is recognizing that booking order determines seat assignment and implementing it efficiently using a SQL window function like ROW_NUMBER().

Q: Flight Occupancy and Waitlist Analysis Python/Java solution

This problem is designed as a SQL database query rather than a typical algorithmic coding problem. The logic can be simulated in Python or Java by sorting bookings per flight and assigning seats sequentially, but the intended solution uses SQL window functions such as ROW_NUMBER().

Q: How to solve Flight Occupancy and Waitlist Analysis in O(n)?

Pure O(n) is generally not achievable in SQL because determining booking order requires sorting by booking_time. The closest practical solution uses ROW_NUMBER() with partitioning, which runs in O(n log n). The query assigns booking order and compares it against flight capacity to separate confirmed and waitlisted passengers.

Q: What is the best approach for Flight Occupancy and Waitlist Analysis?

The most efficient approach uses a SQL window function with ROW_NUMBER(). Partition bookings by flight_id and order by booking_time to determine the booking position for each passenger. Compare the row number with the flight capacity to classify passengers as confirmed or waitlisted, then aggregate counts per flight. This solution runs in about O(n log n) time due to sorting.

Q: Is Flight Occupancy and Waitlist Analysis asked at Google/Amazon/Meta?

Database problems involving seat allocation, ranking, and capacity constraints are common in SQL interviews at companies like Amazon, Meta, and data-focused roles at Google. Variations often test window functions such as ROW_NUMBER, RANK, and partitioned ordering.

Q: What data structure is used in Flight Occupancy and Waitlist Analysis?

The SQL solution relies on analytical window functions rather than traditional data structures. Conceptually, the ordered booking list per flight behaves like a ranked array where ROW_NUMBER() determines seat assignment relative to the flight capacity.

Q: What is the time complexity of Flight Occupancy and Waitlist Analysis?

The optimal SQL solution using ROW_NUMBER() has O(n log n) time complexity because the database sorts bookings within each flight partition. Space complexity is O(n) for the intermediate window function result. A naive correlated subquery approach can degrade to O(n^2).

MediumPremiumFree on FleetCodeDatabase4 min read

Practice this problem

Problem Statement

Table: Flights

+-------------+------+
| Column Name | Type |
+-------------+------+
| flight_id   | int  |
| capacity    | int  |
+-------------+------+
flight_id is the column with unique values for this table.
Each row of this table contains flight id and its capacity.

Table: Passengers

+--------------+------+
| Column Name  | Type |
+--------------+------+
| passenger_id | int  |
| flight_id    | int  |
+--------------+------+
passenger_id is the column with unique values for this table.
Each row of this table contains passenger id and flight id.

Passengers book tickets for flights in advance. If a passenger books a ticket for a flight and there are still empty seats available on the flight, the passenger ticket will be confirmed. However, the passenger will be on a waitlist if the flight is already at full capacity.

Write a solution to report the number of passengers who successfully booked a flight (got a seat) and the number of passengers who are on the waitlist for each flight.

Return the result table ordered by flight_id in ascending order.

The result format is in the following example.

Example 1:

Input: 
Flights table:
+-----------+----------+
| flight_id | capacity |
+-----------+----------+
| 1         | 2        |
| 2         | 2        |
| 3         | 1        |
+-----------+----------+
Passengers table:
+--------------+-----------+
| passenger_id | flight_id |
+--------------+-----------+
| 101          | 1         |
| 102          | 1         |
| 103          | 1         |
| 104          | 2         |
| 105          | 2         |
| 106          | 3         |
| 107          | 3         |
+--------------+-----------+
Output: 
+-----------+------------+--------------+
| flight_id | booked_cnt | waitlist_cnt |
+-----------+------------+--------------+
| 1         | 2          | 1            |
| 2         | 2          | 0            |
| 3         | 1          | 1            |
+-----------+------------+--------------+
Explanation: 
- Flight 1 has a capacity of 2. As there are 3 passengers who have booked tickets, only 2 passengers can get a seat. Therefore, 2 passengers are successfully booked, and 1 passenger is on the waitlist.
- Flight 2 has a capacity of 2. Since there are exactly 2 passengers who booked tickets, everyone can secure a seat. As a result, 2 passengers successfully booked their seats and there are no passengers on the waitlist.
- Flight 3 has a capacity of 1. As there are 2 passengers who have booked tickets, only 1 passenger can get a seat. Therefore, 1 passenger is successfully booked, and 1 passenger is on the waitlist.

Approach Overview

Problem Overview: Each flight has a fixed seat capacity. Passengers book seats over time, and bookings are processed in chronological order. If bookings exceed capacity, extra passengers go to the waitlist. The task is to compute how many passengers are confirmed and how many are waitlisted for every flight.

Approach 1: Correlated Subquery Simulation (O(n^2) time, O(1) space)

A straightforward SQL approach simulates the booking order for each passenger. For every booking row, count how many passengers booked the same flight earlier using a correlated subquery. If that count is less than or equal to the flight capacity, the passenger is confirmed; otherwise they are waitlisted. After assigning the status, aggregate counts per flight. This approach works but performs poorly because each row triggers another scan of the bookings table.

Approach 2: Window Function with ROW_NUMBER (O(n log n) time, O(n) space)

The efficient solution uses a SQL window function. Partition bookings by flight_id and order them by booking_time. Apply ROW_NUMBER() to assign the chronological booking position for every passenger within that flight. Join the result with the flight capacity table and compare the row number with the capacity. If row_number <= capacity, the passenger gets a confirmed seat; otherwise they fall into the waitlist. Finally, group by flight and count confirmed vs waitlisted passengers. Window functions avoid repeated scans and express the booking order directly in a single pass over the sorted dataset.

This approach relies on concepts from database querying and SQL window functions. The key insight is that the seat assignment is simply the booking order relative to capacity.

Recommended for interviews: The window function approach is what interviewers expect for SQL-focused problems. It shows you understand partitioning, ordering, and analytical functions like ROW_NUMBER(). Mentioning the correlated subquery method first demonstrates the baseline logic, while the window function solution shows practical SQL optimization.

Solution

Code

MySQL

Try this approach in the editor →

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Correlated Subquery Simulation	O(n^2)	O(1)	Small datasets or when window functions are unavailable
Window Function with ROW_NUMBER	O(n log n)	O(n)	General case; best SQL solution for ordered seat allocation problems

Video Solution

Leetcode MEDIUM 2783 - Flight Occupancy & Waitlist - Rolling Count in SQL | Everyday Data Science • Everyday Data Science • 603 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Flight Occupancy and Waitlist Analysis easy or hard?

Flight Occupancy and Waitlist Analysis is considered a medium difficulty database problem. The challenge is recognizing that booking order determines seat assignment and implementing it efficiently using a SQL window function like ROW_NUMBER().

Flight Occupancy and Waitlist Analysis Python/Java solution

This problem is designed as a SQL database query rather than a typical algorithmic coding problem. The logic can be simulated in Python or Java by sorting bookings per flight and assigning seats sequentially, but the intended solution uses SQL window functions such as ROW_NUMBER().

How to solve Flight Occupancy and Waitlist Analysis in O(n)?

Pure O(n) is generally not achievable in SQL because determining booking order requires sorting by booking_time. The closest practical solution uses ROW_NUMBER() with partitioning, which runs in O(n log n). The query assigns booking order and compares it against flight capacity to separate confirmed and waitlisted passengers.

What is the best approach for Flight Occupancy and Waitlist Analysis?

The most efficient approach uses a SQL window function with ROW_NUMBER(). Partition bookings by flight_id and order by booking_time to determine the booking position for each passenger. Compare the row number with the flight capacity to classify passengers as confirmed or waitlisted, then aggregate counts per flight. This solution runs in about O(n log n) time due to sorting.

Is Flight Occupancy and Waitlist Analysis asked at Google/Amazon/Meta?

Database problems involving seat allocation, ranking, and capacity constraints are common in SQL interviews at companies like Amazon, Meta, and data-focused roles at Google. Variations often test window functions such as ROW_NUMBER, RANK, and partitioned ordering.

What data structure is used in Flight Occupancy and Waitlist Analysis?

The SQL solution relies on analytical window functions rather than traditional data structures. Conceptually, the ordered booking list per flight behaves like a ranked array where ROW_NUMBER() determines seat assignment relative to the flight capacity.

What is the time complexity of Flight Occupancy and Waitlist Analysis?

The optimal SQL solution using ROW_NUMBER() has O(n log n) time complexity because the database sorts bookings within each flight partition. Space complexity is O(n) for the intermediate window function result. A naive correlated subquery approach can degrade to O(n^2).

Ready to solve this problem?

Practice Flight Occupancy and Waitlist Analysis with our built-in code editor and test cases.

Practice on FleetCode

Combine Two Tables

Second Highest Salary

Problem Info

DifficultyMedium

Acceptance38.0%

Approaches1

Reading time4 min