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.
Given the table name Queue, we can use a SQL query to solve the problem. The key is to sort the rows by the turn column to simulate people boarding the bus in the correct order. Then, we need to compute the cumulative weight as each person boards.
As soon as adding another person's weight exceeds the 1000 kg limit, we know that the last person added was the last allowed on the bus. We can achieve this using a running total and filtering accordingly.
This solution uses an in-memory SQLite database to simulate the Queue table. We first insert the given data into the table. The SQL query uses a common table expression (CTE) named CumulativeWeight to compute a running total of the weights as we order by turn.
The cumulative sum is computed using the window function SUM() OVER (ORDER BY turn). The main query then selects the person_name of the last person whose cumulative weight does not exceed 1000 kg, ordered by turn in descending order to get the last safe person.
Python (using SQL query from Python)
Time Complexity: O(n log n), where n is the number of people, due to sorting.
Space Complexity: O(n) for storing the cumulative weights.
First, we sort the list of people by their 'turn' values, which indicate the order of boarding. Then, starting from the front of the queue, we keep a cumulative sum of weights as people board. When adding a person's weight causes the total weight to exceed the 1000 kg limit, we stop. The last person added before exceeding the limit is the result.
This function first uses the quicksort algorithm to order the people by their turn. It then iterates over the sorted list while accumulating the total weight. The iteration stops when adding another person would exceed the weight capacity, and the name of the last person who could successfully board is returned.
Time Complexity: O(n log n) due to sorting, followed by O(n) for finding the person. Therefore, it's O(n log n) overall.
Space Complexity: O(1) since the space used does not depend on the input size aside from the data structures assumed to not change.
This approach leverages a database operation that uses SQL to determine the last person that can board the bus without exceeding the capacity directly.
This SQL query uses a window function to calculate the cumulative weight as people are considered in boarding order ('turn'). It selects the last person for whom the cumulative weight stays within the limit by ordering the cumulative weights and picking the highest.
SQL
Time Complexity: O(n) for sorting by turn and calculating the cumulative weight.
Space Complexity: O(1), as operations are performed directly on the database.
MySQL
| Approach | Complexity |
|---|---|
| SQL Query Approach | Time Complexity: O(n log n), where n is the number of people, due to sorting. |
| Approach 1: Sorting and Iterative Weight Accumulation | Time Complexity: O(n log n) due to sorting, followed by O(n) for finding the person. Therefore, it's O(n log n) overall. |
| Approach 2: Direct Database Query | Time Complexity: O(n) for sorting by turn and calculating the cumulative weight. |
| Default Approach | — |
| 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 |
Last Person to Fit in the Bus | Leetcode 1204 | Crack SQL Interviews in 50 Qs #mysql #leetcode • Learn With Chirag • 11,047 views views
Watch 9 more video solutions →Practice Last Person to Fit in the Bus with our built-in code editor and test cases.
Practice on FleetCode