LeetCode 2793 - Status of Flight Tickets

LeetCode Problem 2793

Difficulty: 🔴 Hard
Topics: —

Solution

Problem Understanding

This problem asks us to determine whether each passenger's ticket is confirmed or placed on the waitlist, based on the booking order and the capacity of the flight they booked.

We are given two database tables:

The Flights table contains information about each flight and its seating capacity. Each row specifies a unique flight_id and the maximum number of passengers that can be confirmed for that flight.

The Passengers table records ticket bookings. Every passenger has a unique passenger_id, is associated with a flight_id, and has a unique booking_time. The booking time is important because ticket confirmation depends entirely on who booked first.

The confirmation rule is straightforward:

• If a passenger books while seats are still available, their ticket becomes Confirmed.
• If the flight has already reached full capacity at the moment of booking, the passenger is placed on the Waitlist.

In other words, for each flight, passengers must be ordered chronologically by booking_time. The first capacity passengers are confirmed, while everyone after that goes to the waitlist.

The expected output should contain:

• passenger_id
• Status, which is either "Confirmed" or "Waitlist"

The result must be sorted by passenger_id in ascending order.

A key observation is that this is not a traditional algorithmic problem involving arrays or graphs. Instead, it is a SQL ranking problem where we must evaluate a passenger's booking position within their flight.

The problem guarantees several important properties that simplify the implementation:

• flight_id values in Flights are unique.
• passenger_id values are unique.
• booking_time values are unique.

The uniqueness of booking_time is especially important because it guarantees a deterministic booking order. We never need tie breaking logic when ranking passengers for the same flight.

There are several edge cases worth thinking about upfront. A flight may have exactly as many passengers as its capacity, meaning everyone is confirmed. A flight may be overbooked, meaning some passengers become waitlisted. A flight may even have capacity 1, making only the earliest booking valid. Since booking times are unique, we also avoid ambiguity about simultaneous bookings.

Approaches

Brute Force Approach

A straightforward approach would be to process each passenger independently.

For every passenger, we could scan through all other passengers on the same flight and count how many booked earlier. If the number of earlier bookings is smaller than the flight capacity, the passenger is confirmed. Otherwise, they are waitlisted.

This works because the booking priority is determined solely by chronological order. By counting earlier bookings, we effectively determine the passenger's rank for that flight.

However, this approach is inefficient. If there are n passengers, then for every passenger we may scan all other passengers, leading to quadratic complexity. This becomes expensive as the number of passengers grows.

Optimal Approach

The key insight is that we do not need to repeatedly count earlier bookings for every passenger.

Instead, we can assign a ranking within each flight using a SQL window function. Specifically, we partition passengers by flight_id and order them by booking_time.

This gives every passenger a booking sequence number:

• Rank 1 means first booking for the flight.
• Rank 2 means second booking.
• And so on.

Once we know a passenger's booking rank, the decision becomes simple:

• If rank <= capacity, the ticket is Confirmed
• Otherwise, the ticket is Waitlist

This is efficient because SQL window functions are designed exactly for ranking rows within groups.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Compare each passenger against every other passenger on the same flight
Optimal	O(n log n)	O(n)	Use window ranking per flight and compare rank with capacity

Algorithm Walkthrough

1. Join the Passengers table with the Flights table using flight_id.

This gives us access to each flight's capacity alongside every passenger booking. 2. Partition passengers by flight_id.

We want to evaluate booking priority separately for each flight because capacities are independent. 3. Order passengers within each flight by booking_time.

Earlier bookings should get priority, so chronological ordering determines seat allocation. 4. Assign a sequential rank using ROW_NUMBER().

This creates a booking position for every passenger within their flight. Since booking times are unique, the ordering is deterministic. 5. Compare the booking rank with flight capacity.

If the passenger's booking position is within capacity, mark them as "Confirmed". Otherwise, assign "Waitlist". 6. Return only the required columns.

The output should include passenger_id and Status. 7. Sort the result by passenger_id in ascending order.

This satisfies the output requirement.

Why it works

The algorithm works because ROW_NUMBER() correctly models booking priority. For every flight, passengers are ordered chronologically, and each passenger receives an exact booking position. Since the first capacity passengers are guaranteed seats, comparing rank against capacity precisely reproduces the problem's rules. Because booking times are unique, there are no ranking ambiguities, guaranteeing a correct and deterministic result.

Python Solution

# Write your MySQL query statement below

SELECT
    passenger_id,
    CASE
        WHEN booking_rank <= capacity THEN 'Confirmed'
        ELSE 'Waitlist'
    END AS Status
FROM (
    SELECT
        p.passenger_id,
        p.flight_id,
        f.capacity,
        ROW_NUMBER() OVER (
            PARTITION BY p.flight_id
            ORDER BY p.booking_time
        ) AS booking_rank
    FROM Passengers p
    JOIN Flights f
        ON p.flight_id = f.flight_id
) ranked_passengers
ORDER BY passenger_id;

The solution begins by joining Passengers and Flights so that every booking record has access to the corresponding flight capacity.

Inside the subquery, ROW_NUMBER() is used with PARTITION BY p.flight_id. This ensures ranking restarts for every flight. The ORDER BY p.booking_time clause guarantees passengers are ranked chronologically, meaning earlier bookings receive smaller rank values.

After ranking is complete, a CASE statement determines ticket status. Any passenger whose rank is less than or equal to the available capacity receives "Confirmed". Everyone else is assigned "Waitlist".

Finally, the result is ordered by passenger_id to satisfy the problem requirement.

Go Solution

// This problem is SQL-based.
// Submit the following MySQL query in LeetCode:

SELECT
    passenger_id,
    CASE
        WHEN booking_rank <= capacity THEN 'Confirmed'
        ELSE 'Waitlist'
    END AS Status
FROM (
    SELECT
        p.passenger_id,
        p.flight_id,
        f.capacity,
        ROW_NUMBER() OVER (
            PARTITION BY p.flight_id
            ORDER BY p.booking_time
        ) AS booking_rank
    FROM Passengers p
    JOIN Flights f
        ON p.flight_id = f.flight_id
) ranked_passengers
ORDER BY passenger_id;

Since this is a database problem rather than a traditional programming problem, both Python and Go submissions are identical in practice. LeetCode expects a SQL query, so there are no language specific concerns such as slice handling, integer overflow, or memory management.

Worked Examples

Example 1

Input

Flights

flight_id	capacity
1	2
2	2
3	1

Passengers

passenger_id	flight_id	booking_time
101	1	2023-07-10 16:30:00
102	1	2023-07-10 17:45:00
103	1	2023-07-10 12:00:00
104	2	2023-07-05 13:23:00
105	2	2023-07-05 09:00:00
106	3	2023-07-08 11:10:00
107	3	2023-07-08 09:10:00

Step 1: Rank passengers within each flight

For Flight 1, sort by booking time:

Rank	Passenger	Booking Time
1	103	12:00
2	101	16:30
3	102	17:45

Capacity = 2

• Passenger 103 → Confirmed
• Passenger 101 → Confirmed
• Passenger 102 → Waitlist

For Flight 2:

Rank	Passenger	Booking Time
1	105	09:00
2	104	13:23

Capacity = 2

Both passengers are confirmed.

For Flight 3:

Rank	Passenger	Booking Time
1	107	09:10
2	106	11:10

Capacity = 1

• Passenger 107 → Confirmed
• Passenger 106 → Waitlist

Step 2: Sort by passenger_id

passenger_id	Status
101	Confirmed
102	Waitlist
103	Confirmed
104	Confirmed
105	Confirmed
106	Waitlist
107	Confirmed

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Ranking passengers requires sorting bookings within each flight
Space	O(n)	Window function processing stores ranked rows

The dominant cost comes from ordering passengers by booking_time inside each flight partition. In the worst case, if all passengers belong to one flight, this behaves similarly to sorting all rows, leading to O(n log n) complexity. The extra memory usage comes from intermediate ranking structures used by the database engine.

Test Cases

# These represent conceptual SQL validation scenarios.

# Example 1, mixed confirmed and waitlist
# Flight 1: capacity 2, 3 passengers
# Flight 3: capacity 1, later booking waitlisted

# Exact capacity match
# capacity = passengers, everyone confirmed

# Single passenger flight
# capacity = 1, passenger confirmed

# Overbooked flight
# capacity = 1, multiple passengers
# earliest confirmed, rest waitlisted

# Multiple independent flights
# rankings should not mix between flights

# Booking order matters, not passenger_id
# smaller passenger_id booking later still waitlisted

assert True  # Placeholder because SQL problems are tested via database execution

Test	Why
Example 1	Validates mixed confirmation and waitlisting
Exact capacity	Ensures all passengers confirm when seats exactly match demand
Single passenger flight	Tests smallest valid booking scenario
Overbooked flight	Ensures only earliest bookings are confirmed
Multiple flights	Verifies partitioning by flight_id
Booking order vs passenger_id	Confirms booking time determines priority

Edge Cases

Flight capacity exactly equals passenger count

A common source of bugs is using a strict inequality such as rank < capacity instead of rank <= capacity. If a flight has exactly enough seats for all passengers, everyone should still be confirmed. The implementation correctly uses <=, ensuring the last available seat is assigned properly.

Heavy overbooking

Some flights may have significantly more bookings than available seats. A naive implementation could repeatedly recount earlier bookings, becoming inefficient. The ranking approach handles this naturally because every passenger receives a booking order exactly once, and all later passengers automatically become waitlisted.

Booking order differs from passenger ID

It is easy to mistakenly assume lower passenger_id values imply earlier booking priority. The problem explicitly states that confirmation depends on booking_time. The implementation ranks exclusively by booking time, ensuring the correct passenger receives the seat regardless of ID ordering.

Flights with capacity one

Flights with only one seat are especially sensitive because only the earliest booking should be confirmed. Since ROW_NUMBER() assigns the earliest booking rank 1, comparing it against capacity 1 guarantees exactly one confirmed passenger and correct waitlisting for all others.