LeetCode 2783 - Flight Occupancy and Waitlist Analysis

This problem models airline flight bookings with limited seating capacity. The Flights table contains one row per flight. Each flight has a unique flightid and a capacity, which represents the maximum number of passengers that can be seated on that flight.

leetcodemediumdatabase

LeetCode Problem 2783

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem models airline flight bookings with limited seating capacity.

The Flights table contains one row per flight. Each flight has a unique flight_id and a capacity, which represents the maximum number of passengers that can be seated on that flight.

The Passengers table contains one row per passenger booking. Each passenger is associated with exactly one flight through flight_id.

The booking rule is straightforward:

  • If the number of passengers booking a flight is less than or equal to the flight's capacity, every passenger receives a confirmed seat.
  • If the number of passengers exceeds the flight's capacity, only up to capacity passengers can be seated, and the remaining passengers are placed on a waitlist.

For every flight, we must calculate:

  • booked_cnt, the number of passengers who successfully receive a seat.
  • waitlist_cnt, the number of passengers who cannot receive a seat because the flight is already full.

The result must be returned for every flight and sorted by flight_id in ascending order.

The important observation is that the identity of the passengers does not matter. We only need the total number of passenger bookings for each flight. Once we know:

  • flight capacity
  • total passengers booked

we can directly compute:

  • booked_cnt = min(total_passengers, capacity)
  • waitlist_cnt = max(total_passengers - capacity, 0)

A few edge cases are worth considering:

  • A flight may have no passengers at all.
  • A flight may have exactly as many passengers as seats.
  • A flight may have more passengers than seats.
  • A flight may have a capacity larger than the number of bookings.
  • Every flight from the Flights table must appear in the output, even if no passengers booked it.

Since this is a database problem, the main task is aggregating passenger counts per flight and combining those counts with flight capacities.

Approaches

Brute Force

A brute force solution would process each flight individually and scan the entire Passengers table to count how many passengers booked that flight.

For every flight:

  1. Iterate through all passengers.
  2. Count passengers whose flight_id matches the current flight.
  3. Compute booked and waitlisted counts using the capacity.

This approach is correct because it explicitly counts all bookings for every flight. However, it repeatedly scans the passenger table, which becomes inefficient when the number of flights and passengers grows.

Optimal Approach

The key observation is that we only need the number of passengers per flight.

Instead of scanning all passengers for every flight, we can first aggregate passenger counts grouped by flight_id. After obtaining the count for each flight, we join those counts with the Flights table.

Once the total passenger count is known:

  • Confirmed bookings are limited by capacity.
  • Waitlisted passengers are the excess beyond capacity.

In SQL, this translates naturally into:

  1. Group passengers by flight_id.
  2. Left join the aggregated counts with flights.
  3. Apply LEAST and conditional arithmetic to compute the two required values.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(F × P) O(1) Scan all passengers for every flight
Optimal O(F + P) O(F) Aggregate passenger counts once, then join

Where:

  • F = number of flights
  • P = number of passengers

Algorithm Walkthrough

Optimal SQL Algorithm

  1. Group the Passengers table by flight_id and count the number of passengers for each flight. This produces the total bookings per flight.
  2. Perform a LEFT JOIN between Flights and the aggregated passenger counts. A left join is required because flights with zero passengers must still appear in the result.
  3. Replace any missing passenger count with 0 using COALESCE.
  4. Compute the number of confirmed bookings using:

MIN(passenger_count, capacity)

This ensures that confirmed passengers never exceed available seats. 5. Compute the waitlist count using:

MAX(passenger_count - capacity, 0)

This counts only passengers beyond the available capacity. 6. Return the results ordered by flight_id.

Why it works

The total number of bookings for a flight completely determines the answer. If a flight has p passengers and capacity c, exactly min(p, c) passengers can be seated, because the number of occupied seats cannot exceed either the number of passengers or the capacity. Any remaining passengers, max(p - c, 0), must be placed on the waitlist. Since the algorithm computes the exact booking count for every flight and applies these formulas directly, the result is always correct.

Python Solution

Although LeetCode classifies this as a Database problem and expects SQL, the following Python implementation demonstrates the equivalent logic.

from collections import defaultdict
from typing import List

class Solution:
    def flightOccupancyAndWaitlistAnalysis(
        self,
        flights: List[List[int]],
        passengers: List[List[int]]
    ) -> List[List[int]]:
        passenger_count = defaultdict(int)

        for _, flight_id in passengers:
            passenger_count[flight_id] += 1

        result = []

        for flight_id, capacity in sorted(flights):
            total = passenger_count[flight_id]

            booked_cnt = min(total, capacity)
            waitlist_cnt = max(total - capacity, 0)

            result.append([flight_id, booked_cnt, waitlist_cnt])

        return result

The implementation begins by counting how many passengers booked each flight using a hash map. The key is the flight ID and the value is the number of bookings.

After the aggregation phase, each flight is processed exactly once. For every flight, the total passenger count is retrieved from the hash map. The confirmed booking count is the smaller of the passenger count and the capacity. The waitlist count is the excess beyond capacity, if any.

This mirrors the SQL logic exactly and avoids repeatedly scanning the passenger list.

SQL Solution

SELECT
    f.flight_id,
    LEAST(COALESCE(p.passenger_cnt, 0), f.capacity) AS booked_cnt,
    GREATEST(COALESCE(p.passenger_cnt, 0) - f.capacity, 0) AS waitlist_cnt
FROM Flights f
LEFT JOIN (
    SELECT
        flight_id,
        COUNT(*) AS passenger_cnt
    FROM Passengers
    GROUP BY flight_id
) p
ON f.flight_id = p.flight_id
ORDER BY f.flight_id;

Go Solution

package main

import "sort"

func flightOccupancyAndWaitlistAnalysis(
	flights [][]int,
	passengers [][]int,
) [][]int {
	passengerCount := make(map[int]int)

	for _, passenger := range passengers {
		flightID := passenger[1]
		passengerCount[flightID]++
	}

	sort.Slice(flights, func(i, j int) bool {
		return flights[i][0] < flights[j][0]
	})

	result := make([][]int, 0, len(flights))

	for _, flight := range flights {
		flightID := flight[0]
		capacity := flight[1]

		total := passengerCount[flightID]

		bookedCnt := total
		if bookedCnt > capacity {
			bookedCnt = capacity
		}

		waitlistCnt := 0
		if total > capacity {
			waitlistCnt = total - capacity
		}

		result = append(result, []int{
			flightID,
			bookedCnt,
			waitlistCnt,
		})
	}

	return result
}

The Go implementation follows the same strategy as the Python version. A map is used to store booking counts per flight. Since Go does not provide built in min and max functions for integers, simple conditional statements are used to compute the booked and waitlisted counts. Missing map entries automatically evaluate to zero, which naturally handles flights with no passengers.

Worked Examples

Example 1

Flights:

flight_id capacity
1 2
2 2
3 1

Passengers:

passenger_id flight_id
101 1
102 1
103 1
104 2
105 2
106 3
107 3

Step 1, Count Passengers Per Flight

flight_id passenger_count
1 3
2 2
3 2

Step 2, Process Each Flight

Flight 1

Value Result
Capacity 2
Passengers 3
booked_cnt min(3, 2) = 2
waitlist_cnt max(3 - 2, 0) = 1

Flight 2

Value Result
Capacity 2
Passengers 2
booked_cnt min(2, 2) = 2
waitlist_cnt max(2 - 2, 0) = 0

Flight 3

Value Result
Capacity 1
Passengers 2
booked_cnt min(2, 1) = 1
waitlist_cnt max(2 - 1, 0) = 1

Final Output

flight_id booked_cnt waitlist_cnt
1 2 1
2 2 0
3 1 1

Complexity Analysis

Measure Complexity Explanation
Time O(F + P) Count passengers once and process each flight once
Space O(F) Store passenger counts per flight

The aggregation phase scans the passenger table exactly once, producing one count entry per flight. The second phase processes each flight exactly once. Therefore the total running time is linear in the size of the input. The extra memory usage comes from the hash map storing passenger counts for each flight.

Test Cases

from collections import defaultdict

def solve(flights, passengers):
    passenger_count = defaultdict(int)

    for _, flight_id in passengers:
        passenger_count[flight_id] += 1

    result = []

    for flight_id, capacity in sorted(flights):
        total = passenger_count[flight_id]

        result.append([
            flight_id,
            min(total, capacity),
            max(total - capacity, 0)
        ])

    return result

# Example from statement
assert solve(
    [[1, 2], [2, 2], [3, 1]],
    [
        [101, 1],
        [102, 1],
        [103, 1],
        [104, 2],
        [105, 2],
        [106, 3],
        [107, 3]
    ]
) == [
    [1, 2, 1],
    [2, 2, 0],
    [3, 1, 1]
]  # mixed booked and waitlisted passengers

assert solve(
    [[1, 5]],
    []
) == [
    [1, 0, 0]
]  # no passengers

assert solve(
    [[1, 3]],
    [[1, 1], [2, 1], [3, 1]]
) == [
    [1, 3, 0]
]  # exactly full

assert solve(
    [[1, 2]],
    [[1, 1], [2, 1], [3, 1], [4, 1]]
) == [
    [1, 2, 2]
]  # more passengers than capacity

assert solve(
    [[1, 10]],
    [[1, 1], [2, 1]]
) == [
    [1, 2, 0]
]  # capacity much larger than bookings

assert solve(
    [[1, 1], [2, 2]],
    [[1, 1]]
) == [
    [1, 1, 0],
    [2, 0, 0]
]  # one flight has no passengers

Test Summary

Test Why
Problem example Validates normal mixed behavior
No passengers Ensures zero counts are handled
Capacity equals bookings Verifies no waitlist is created
Capacity smaller than bookings Verifies waitlist calculation
Capacity much larger than bookings Verifies booking count is not capped incorrectly
Flight with zero bookings Ensures all flights appear in output

Edge Cases

Flights With No Passengers

A flight may exist in the Flights table but have no corresponding rows in the Passengers table. This is a common source of bugs when using an inner join because the flight could disappear from the result. The solution uses a LEFT JOIN and COALESCE, ensuring such flights remain in the output with both counts equal to zero.

Passenger Count Exactly Equal to Capacity

When the number of bookings exactly matches the capacity, every passenger receives a seat and nobody is waitlisted. An incorrect implementation might use a strict comparison and accidentally place passengers on the waitlist. Using min(total, capacity) and max(total - capacity, 0) handles this case naturally.

Passenger Count Exceeds Capacity

When bookings exceed available seats, only up to the capacity can be confirmed. The remaining passengers belong on the waitlist. A common mistake is to report the total passenger count as booked. The solution explicitly caps confirmed bookings at capacity and places the excess in the waitlist count.

Capacity Greater Than Passenger Count

When a flight has more seats than bookings, all passengers should be confirmed and the waitlist should be zero. The max(total - capacity, 0) calculation prevents negative waitlist values and correctly reports zero.

Multiple Flights With Different Booking Patterns

Some flights may be underbooked, some exactly full, and others overbooked. Since the aggregation is performed independently per flight, the calculations for one flight never affect another, guaranteeing correctness across mixed scenarios.