Watch 2 video solutions for The Number of Passengers in Each Bus I, a medium level problem involving Database. This walkthrough by Everyday Data Science has 815 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Table: Buses
+--------------+------+ | Column Name | Type | +--------------+------+ | bus_id | int | | arrival_time | int | +--------------+------+ bus_id is the column with unique values for this table. Each row of this table contains information about the arrival time of a bus at the LeetCode station. No two buses will arrive at the same time.
Table: Passengers
+--------------+------+ | Column Name | Type | +--------------+------+ | passenger_id | int | | arrival_time | int | +--------------+------+ passenger_id is the column with unique values for this table. 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 time tbus and a passenger arrived at time tpassenger where tpassenger <= tbus and the passenger did not catch any bus, the passenger will use that 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 | +--------+--------------+ | 1 | 2 | | 2 | 4 | | 3 | 7 | +--------+--------------+ Passengers table: +--------------+--------------+ | passenger_id | arrival_time | +--------------+--------------+ | 11 | 1 | | 12 | 5 | | 13 | 6 | | 14 | 7 | +--------------+--------------+ Output: +--------+----------------+ | bus_id | passengers_cnt | +--------+----------------+ | 1 | 1 | | 2 | 0 | | 3 | 3 | +--------+----------------+ Explanation: - Passenger 11 arrives at time 1. - Bus 1 arrives at time 2 and collects passenger 11. - Bus 2 arrives at time 4 and does not collect any passengers. - 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, 13, and 14.
Problem Overview: You receive two tables: Buses with bus arrival times and Passengers with passenger arrival times. Each passenger boards the earliest bus whose arrival_time is greater than or equal to the passenger’s arrival. The task is to compute how many passengers board each bus.
Approach 1: Correlated Subquery to Find the Earliest Valid Bus (O(P * B) time, O(1) space)
For every passenger, determine the first bus they can catch. A correlated subquery selects MIN(b.arrival_time) from Buses where the bus arrival is greater than or equal to the passenger’s arrival. This effectively maps each passenger to the earliest valid bus. After identifying that bus time, join it back to the Buses table and group by bus_id to count passengers. The idea mirrors a greedy assignment: each passenger takes the earliest possible bus.
Approach 2: Join + Aggregation with Precomputed Bus Mapping (O(P log B) time, O(P) space)
Instead of recalculating the earliest bus repeatedly, compute a mapping between passengers and buses using a join condition b.arrival_time >= p.arrival_time. Then group by passenger and select the minimum bus arrival using MIN(). This step identifies the exact bus each passenger boards. Finally, aggregate counts per bus with GROUP BY bus_id. Most SQL engines optimize this pattern well using indexes on arrival_time, making it efficient for large datasets.
Both strategies rely on relational operations such as joins, grouping, and aggregate functions. Understanding how to express "earliest valid match" in SQL is the key insight. The pattern appears frequently in scheduling and allocation queries, which is why it’s commonly grouped under database and SQL practice problems. Variants may also use window functions to rank candidate buses per passenger.
Recommended for interviews: The join + aggregation approach. It shows you understand relational matching and aggregation patterns without relying heavily on nested subqueries. Writing the correlated subquery first helps demonstrate the logic clearly, while the optimized join-based solution shows stronger SQL fluency.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Correlated Subquery (MIN Bus Lookup) | O(P * B) | O(1) | Clear logic and easy to write when datasets are small |
| Join + MIN Aggregation | O(P log B) | O(P) | Preferred for larger tables with indexes on arrival_time |
| Window Function Ranking | O(P log B) | O(P) | Useful when ranking candidate buses per passenger using ROW_NUMBER() |
