Skip to main content
Talentd

Last Person to Fit in the Bus - Solution & Explanation

MediumDatabase13 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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    | ___          |
+------+----+-----------+--------+--------------+

Approach Overview

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 1: SQL Query Approach

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.

Code

Python (using SQL query from Python)

Python (using SQL query from Python)

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 1: Sorting and Iterative Weight Accumulation

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Approach 2: Direct Database Query

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.

Code

SQL

SQL

Complexity

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.

Try this approach in the editor →

Approach 4: Default Approach

Code

MySQL

MySQL

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
SQL Query Approach

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.

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.
Space Complexity: O(1) since the space used does not depend on the input size aside from the data structures assumed to not change.

Approach 2: Direct Database Query

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.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting and Iterative Weight AccumulationO(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

Video Solution

Last Person to Fit in the Bus | Leetcode 1204 | Crack SQL Interviews in 50 Qs #mysql #leetcode • Learn With Chirag • 12,319 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Last Person to Fit in the Bus easy or hard?
The problem is rated Medium because the logic is simple but requires recognizing the cumulative constraint. SQL users must know how to apply window functions, while programming solutions require careful simulation of the boarding sequence with prefix sums.
Last Person to Fit in the Bus Python/Java solution
In Python or Java, sort passengers by their turn value and iterate through the list while maintaining a running total of weights. Add each passenger's weight to the cumulative sum and stop when the sum would exceed 1000. The last valid passenger before exceeding the limit is the answer.
How to solve Last Person to Fit in the Bus in O(n)?
Use a cumulative running total with a SQL window function. Compute SUM(weight) OVER (ORDER BY turn) to track the total weight after each passenger boards. Then filter rows where the cumulative sum is ≤ 1000 and return the passenger with the maximum turn among them.
What is the best approach for Last Person to Fit in the Bus?
The most efficient solution uses an SQL window function to compute a cumulative sum of passenger weights ordered by turn. After calculating SUM(weight) OVER (ORDER BY turn), filter rows where the cumulative weight is ≤ 1000 and return the passenger with the largest turn. This directly identifies the last valid passenger in O(n) time after ordering.
Is Last Person to Fit in the Bus asked at Google/Amazon/Meta?
Problems involving window functions, cumulative sums, and ordered aggregations appear frequently in SQL interviews at large tech companies. Variants of this question test familiarity with analytical SQL queries and real-world database data processing patterns.
What data structure is used in Last Person to Fit in the Bus?
The core idea relies on a running cumulative sum rather than a complex data structure. In programming implementations, you iterate through a sorted list and maintain a prefix sum of weights. In SQL, the equivalent concept is implemented with a window function.
What is the time complexity of Last Person to Fit in the Bus?
The SQL window function solution runs in O(n) time for scanning rows once the ordering is applied. The iterative programming approach typically requires sorting by turn first, resulting in O(n log n) time. Both approaches use O(1) additional space.

Ready to solve this problem?

Practice Last Person to Fit in the Bus with our built-in code editor and test cases.

Practice on FleetCode
Previous

Running Total for Different Genders

Next

The Number of Seniors and Juniors to Join the Company