Watch 10 video solutions for Last Person to Fit in the Bus, a medium level problem involving Database. This walkthrough by Learn With Chirag has 11,047 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Table: Queue
+-------------+---------+ | Column Name | Type | +-------------+---------+ | person_id | int | | person_name | varchar | | weight | int | | turn | int | +-------------+---------+ person_id column contains unique values. This table has the information about all people waiting for a bus. The person_id and turn columns will contain all numbers from 1 to n, where n is the number of rows in the table. turn determines the order of which the people will board the bus, where turn=1 denotes the first person to board and turn=n denotes the last person to board. weight is the weight of the person in kilograms.
There is a queue of people waiting to board a bus. However, the bus has a weight limit of 1000 kilograms, so there may be some people who cannot board.
Write a solution to find the person_name of the last person that can fit on the bus without exceeding the weight limit. The test cases are generated such that the first person does not exceed the weight limit.
Note that only one person can board the bus at any given turn.
The result format is in the following example.
Example 1:
Input: Queue table: +-----------+-------------+--------+------+ | person_id | person_name | weight | turn | +-----------+-------------+--------+------+ | 5 | Alice | 250 | 1 | | 4 | Bob | 175 | 5 | | 3 | Alex | 350 | 2 | | 6 | John Cena | 400 | 3 | | 1 | Winston | 500 | 6 | | 2 | Marie | 200 | 4 | +-----------+-------------+--------+------+ Output: +-------------+ | person_name | +-------------+ | John Cena | +-------------+ Explanation: The folowing table is ordered by the turn for simplicity. +------+----+-----------+--------+--------------+ | Turn | ID | Name | Weight | Total Weight | +------+----+-----------+--------+--------------+ | 1 | 5 | Alice | 250 | 250 | | 2 | 3 | Alex | 350 | 600 | | 3 | 6 | John Cena | 400 | 1000 | (last person to board) | 4 | 2 | Marie | 200 | 1200 | (cannot board) | 5 | 4 | Bob | 175 | ___ | | 6 | 1 | Winston | 500 | ___ | +------+----+-----------+--------+--------------+
Problem Overview: A queue of passengers wants to board a bus with a total weight limit of 1000. Each passenger has a weight and a boarding order (turn). Passengers board sequentially, and once the cumulative weight exceeds the limit, boarding stops. The task is to return the name of the last person who successfully boards without exceeding the capacity.
Approach 1: Sorting and Iterative Weight Accumulation (O(n log n) time, O(1) space)
Start by ordering passengers by their turn value to simulate the real boarding sequence. Then iterate through the list while maintaining a running cumulative weight. For each passenger, add their weight to the total and check whether the sum stays within 1000. The moment the sum would exceed the limit, stop the iteration—the previous passenger is the last one who fits. This approach mirrors how the queue actually behaves and is easy to implement in general programming languages. The main cost comes from sorting the records, making the time complexity O(n log n) with constant extra space.
Approach 2: Direct Database Query with Window Functions (O(n) time, O(1) space)
SQL can solve this more elegantly using a cumulative sum. First sort rows by turn, then compute a running total using a window function like SUM(weight) OVER (ORDER BY turn). This produces the cumulative weight after each passenger boards. Filter rows where the cumulative weight is less than or equal to 1000, and select the passenger with the largest turn. The database engine performs the iteration internally, resulting in an efficient linear scan after ordering. This approach is common in database interview questions involving ordered aggregation and running totals.
The key insight is recognizing that the constraint depends on a prefix sum of weights. Instead of checking combinations, you only track the cumulative weight as passengers board in order. Problems involving sequential accumulation often reduce to prefix sums or running totals, concepts frequently used alongside sorting and analytical queries in database problems.
Recommended for interviews: Interviewers usually expect the SQL window function solution because it demonstrates knowledge of analytical queries and cumulative aggregation. The iterative approach still shows strong problem understanding and is useful when solving the problem in languages like Python or Java where you simulate the queue logic directly.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Iterative Weight Accumulation | O(n log n) | O(1) | When implementing the logic in general languages like Python, Java, or C++ |
| SQL Window Function (Running Sum) | O(n) | O(1) | Best for database environments where cumulative sums can be computed with window functions |
