The Number of Passengers in Each Bus I - Solution & Explanation

MediumPremiumFree on FleetCodeDatabase4 min read

Problem Statement

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 t_bus and a passenger arrived at time t_passenger where t_passenger <= t_bus 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.

Approach Overview

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.

Solution

Code

MySQL

Try this approach in the editor →

Detailed Complexity Analysis

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()

Video Solution

Leetcode MEDIUM 2142 - Number of Passengers in Each Bus 1 - SQL Explained by Everyday Data Science • Everyday Data Science • 874 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is The Number of Passengers in Each Bus I easy or hard?

The problem is generally classified as Medium difficulty. The challenge is expressing the "earliest valid match" condition correctly in SQL while keeping the query efficient. Candidates familiar with joins and aggregation typically solve it quickly.

The Number of Passengers in Each Bus I Python/Java solution

This problem is designed for SQL databases, but the logic can be replicated in Python or Java by sorting buses and passengers by arrival time. For each passenger, binary search can locate the earliest bus they can board, and a counter array tracks how many passengers board each bus.

How to solve The Number of Passengers in Each Bus I in O(n)?

Pure O(n) is uncommon in SQL because the query must match passengers with candidate buses. The closest practical solution uses indexed joins on arrival_time and aggregation, which behaves near O(P log B) in most databases. Efficient indexing significantly reduces the lookup cost for each passenger.

What is the best approach for The Number of Passengers in Each Bus I?

The most practical solution uses a SQL join between passengers and buses with a condition that the bus arrival time is greater than or equal to the passenger arrival. After joining, use MIN(bus arrival) per passenger to identify the earliest bus and then aggregate counts per bus. With indexing on arrival_time, this approach performs efficiently and keeps the query readable.

Is The Number of Passengers in Each Bus I asked at Google/Amazon/Meta?

Database allocation and scheduling queries like this appear in SQL interview rounds at companies such as Amazon, Google, and Meta. The exact problem may vary, but the pattern of assigning each record to the earliest valid event and aggregating results is common in analytics and backend data tasks.

What data structure is used in The Number of Passengers in Each Bus I?

The problem is solved using relational database tables and SQL operations rather than traditional data structures. Key operations include joins, aggregation with MIN(), and GROUP BY. Indexes on arrival_time act like search structures that speed up matching passengers to buses.

What is the time complexity of The Number of Passengers in Each Bus I?

The complexity depends on the SQL strategy. A correlated subquery approach can behave like O(P * B) where P is passengers and B is buses. A join with indexed lookups typically runs around O(P log B) because the database can quickly locate the earliest valid bus using the arrival_time index.

Ready to solve this problem?

Practice The Number of Passengers in Each Bus I with our built-in code editor and test cases.

Practice on FleetCode

Combine Two Tables

Second Highest Salary

Problem Info

DifficultyMedium

Acceptance48.8%

Approaches1

Reading time4 min

Practice this problem

Open in Editor