Table: Buses
+--------------+------+ | Column Name | Type | +--------------+------+ | bus_id | int | | arrival_time | int | | capacity | int | +--------------+------+ bus_id contains unique values. Each row of this table contains information about the arrival time of a bus at the LeetCode station and its capacity (the number of empty seats it has). No two buses will arrive at the same time and all bus capacities will be positive integers.
Table: Passengers
+--------------+------+ | Column Name | Type | +--------------+------+ | passenger_id | int | | arrival_time | int | +--------------+------+ passenger_id contains unique values. Each row of this table contains information about the arrival time of a passenger at the LeetCode station.
Buses and passengers arrive at the LeetCode station. If a bus arrives at the station at a time tbus and a passenger arrived at a time tpassenger where tpassenger <= tbus and the passenger did not catch any bus, the passenger will use that bus. In addition, each bus has a capacity. If at the moment the bus arrives at the station there are more passengers waiting than its capacity capacity, only capacity passengers will use the bus.
Write a solution to report the number of users that used each bus.
Return the result table ordered by bus_id in ascending order.
The result format is in the following example.
Example 1:
Input: Buses table: +--------+--------------+----------+ | bus_id | arrival_time | capacity | +--------+--------------+----------+ | 1 | 2 | 1 | | 2 | 4 | 10 | | 3 | 7 | 2 | +--------+--------------+----------+ Passengers table: +--------------+--------------+ | passenger_id | arrival_time | +--------------+--------------+ | 11 | 1 | | 12 | 1 | | 13 | 5 | | 14 | 6 | | 15 | 7 | +--------------+--------------+ Output: +--------+----------------+ | bus_id | passengers_cnt | +--------+----------------+ | 1 | 1 | | 2 | 1 | | 3 | 2 | +--------+----------------+ Explanation: - Passenger 11 arrives at time 1. - Passenger 12 arrives at time 1. - Bus 1 arrives at time 2 and collects passenger 11 as it has one empty seat. - Bus 2 arrives at time 4 and collects passenger 12 as it has ten empty seats. - Passenger 12 arrives at time 5. - Passenger 13 arrives at time 6. - Passenger 14 arrives at time 7. - Bus 3 arrives at time 7 and collects passengers 12 and 13 as it has two empty seats.
Problem Overview: You have two tables: buses with an arrival time and capacity, and passengers with their arrival time. Each passenger boards the earliest bus that arrives after them if seats are available. Passengers who cannot board because the bus is full wait for the next one. The goal is to return how many passengers board each bus.
Approach 1: Direct Simulation with Joins (Brute Force) (Time: O(B × P), Space: O(1))
The most straightforward idea is to simulate the boarding process. For every bus, find passengers whose arrival_time is less than or equal to the bus arrival and who have not boarded a previous bus. Then assign them until the bus capacity is reached. In SQL this often requires repeated joins or correlated subqueries to filter passengers that were not previously assigned. The approach works conceptually but scales poorly because each bus repeatedly scans the passenger table.
Approach 2: Window Functions with Prefix Passenger Counts (Optimized SQL) (Time: O((B + P) log(B + P)), Space: O(B))
The efficient approach converts the simulation into a counting problem. First, compute how many passengers have arrived by the time each bus appears using a cumulative count. This can be done with a grouped join between buses and passengers or a subquery that counts passengers with arrival_time <= bus_time. Then use a window function to track how many passengers were already boarded by earlier buses.
For each bus, the number of passengers waiting equals total_arrived_so_far - total_boarded_before. The actual number boarding that bus is LEAST(capacity, waiting_passengers). A window function such as LAG or a running SUM() keeps track of the cumulative boarded passengers from previous buses. This transforms the problem into simple arithmetic on prefix counts instead of row-by-row simulation.
This pattern appears frequently in database interview questions: convert sequential processes into cumulative metrics. Window functions in SQL are particularly useful because they let you compute running totals without procedural loops.
Recommended for interviews: The window-function approach. Interviewers expect you to recognize that passengers form a queue and that the number boarding each bus depends only on cumulative arrivals and previously used capacity. Explaining the brute-force simulation shows you understand the boarding rules, but converting it into prefix counts demonstrates strong SQL reasoning and familiarity with window functions.
MySQL
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation with Joins | O(B × P) | O(1) | Small datasets or when demonstrating the boarding logic step-by-step |
| Window Functions + Prefix Passenger Counts | O((B + P) log(B + P)) | O(B) | Production SQL queries and interview solutions requiring scalable passenger allocation |
Leetcode Problem - 2153. The Number of Passengers in Each Bus II - Part 1 | SQL | Hard Question • Byte Blusters • 140 views views
Practice The Number of Passengers in Each Bus II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor