Skip to main content
Talentd

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

HardPremiumFree on FleetCodeDatabase5 min read
Practice this problem

Problem Statement

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.

Approach Overview

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.

Solution

Code

MySQL

MySQL

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Simulation with JoinsO(B × P)O(1)Small datasets or when demonstrating the boarding logic step-by-step
Window Functions + Prefix Passenger CountsO((B + P) log(B + P))O(B)Production SQL queries and interview solutions requiring scalable passenger allocation

Video Solution

Leetcode Problem - 2153. The Number of Passengers in Each Bus II - Part 1 | SQL | Hard Question • Byte Blusters • 144 views views

Frequently Asked Questions

Is The Number of Passengers in Each Bus II easy or hard?
The problem is rated Hard because it requires translating a sequential boarding process into a set-based SQL query. Understanding cumulative counts, window functions, and capacity constraints is necessary to produce a correct and scalable solution.
The Number of Passengers in Each Bus II Python/Java solution
The original problem is designed as a SQL query question rather than a typical algorithmic coding task. A procedural Python or Java solution would simulate the queue by sorting buses and passengers by arrival time and maintaining a pointer or queue to track waiting passengers.
How to solve The Number of Passengers in Each Bus II in O(n)?
Treat the boarding process as prefix counting instead of simulation. Count how many passengers have arrived before each bus, maintain a running total of passengers already boarded, and compute remaining waiting passengers. The number boarding the current bus is min(capacity, waiting_passengers). With pre-sorted data and indexes, the window computation becomes effectively linear.
What is the best approach for The Number of Passengers in Each Bus II?
The best approach uses SQL window functions with cumulative passenger counts. Compute how many passengers have arrived before each bus, track how many have already boarded previous buses, and assign the remaining passengers up to the bus capacity using LEAST(). This avoids row-by-row simulation and runs in roughly O((B + P) log(B + P)) time depending on indexing and sorting.
Is The Number of Passengers in Each Bus II asked at Google/Amazon/Meta?
Database-style query problems that require window functions and cumulative metrics appear frequently in SQL interviews at companies like Amazon, Google, and Meta. Variants of queue simulation and capacity allocation are common patterns used to test SQL reasoning.
What data structure is used in The Number of Passengers in Each Bus II?
The solution primarily relies on relational database operations rather than traditional data structures. Window functions, prefix sums, and ordered scans over arrival times act as the main mechanisms for tracking passenger counts.
What is the time complexity of The Number of Passengers in Each Bus II?
The optimized SQL solution runs in about O((B + P) log(B + P)) time due to sorting or index lookups on arrival times. The window function then processes buses in linear order. A naive simulation using repeated joins can degrade to O(B × P).

Ready to solve this problem?

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

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary