Last Person to Fit in the Bus | Leetcode 1204

This chapter breaks down Leetcode Problem 1204: Last Person to Fit in the Bus, exploring how to calculate a running cumulative total (running sum) in SQL using a self-join, group aggregation, and conditional filtering (HAVING) to find the threshold boundary.

1. Problem Statement & Schema Overview

We are given a queue of people waiting to board a bus. The bus has a strict weight limit of 1000 kilograms. Our objective is to write a SQL query to find the person_name of the last person who can board the bus without exceeding the 1000 kg total weight limit.

Table Schema: Queue

• person_id (int): Primary key containing unique values.
• person_name (varchar): Name of the waiting person.
• weight (int): Weight of the individual in kilograms.
• turn (int): Determines the boarding order, running sequentially from 1 to n (where n is the total number of rows).

Real-Life Analogy: Boarding a Limited-Capacity Elevator

Analogy: Imagine a group of people standing in line outside an elevator with a maximum load capacity of 1000 kg. People step in one by one in numerical order (turn = 1, 2, 3...). As each person enters, an attendant adds up their weight to check the running total. The moment adding the next person's weight pushes the total past 1000 kg, the attendant stops the queue. The person who stepped in right before that limit was crossed is our answer.

2. Step-by-Step Manual Walkthrough

Let's examine a sample dataset to see how boarding sequence and cumulative weight interact.

Simulating Cumulative Boarding Weights

If we evaluate the people in ascending order of their turn and accumulate their weights:

Conclusion from Walkthrough: The last person who successfully fits into the bus without exceeding 1000 kg is John Cena.

3. The Core Challenge: Calculating Cumulative Sums in SQL

In standard programming languages, calculating a running total is straightforward using a loop. In SQL (especially across varying SQL dialects), we need a strategy to accumulate rows dynamically.

The strategy demonstrated in this lecture is the Self-Join Cumulative Sum Pattern, where we join the table to itself to look backward at all preceding turns for any given row.

4. Constructing the Self-Join

To calculate how much total weight has accumulated up to and including a specific person's turn, we can join the Queue table (q1) with another instance of itself (q2).

SELECT *
FROM Queue q1
JOIN Queue q2
  ON q1.turn >= q2.turn;

How the Self-Join Works

• q1 represents the current person currently being evaluated.
• q2 represents all people whose turn is less than or equal to q1's turn (i.e., people who boarded before or at the same time as q1).
• By setting the join condition to q1.turn >= q2.turn, for every single row in q1, we pull in all preceding rows from q2.

5. Grouping and Filtering with HAVING

Because joining q1 and q2 creates multiple matching rows for each person, we must group our results by q1.turn and sum up the corresponding weights from q2.

SELECT q1.person_name, q1.turn, SUM(q2.weight) AS cumulative_weight
FROM Queue q1
JOIN Queue q2
  ON q1.turn >= q2.turn
GROUP BY q1.turn, q1.person_name
HAVING SUM(q2.weight) <= 1000;

Note on WHERE vs HAVING: We use HAVING instead of WHERE here because the weight restriction applies to an aggregated value (SUM(q2.weight)), which is computed after the GROUP BY clause has executed. WHERE filters individual rows before aggregation, whereas HAVING filters groups after aggregation.

6. Ordering and Limiting to Find the Last Person

After applying the HAVING SUM(q2.weight) <= 1000 filter, our query returns all valid rows where the cumulative weight is within the 1000 kg limit. However, the last person to fit might appear anywhere depending on the database engine execution order.

To guarantee we always grab the person with the highest valid turn (the last person who boarded):

1. Sort the results in descending order based on the cumulative weight or turn (ORDER BY SUM(q2.weight) DESC).
2. Limit the output to 1 using the LIMIT 1 keyword (LIMIT / TOP depending on your SQL dialect).

SELECT q1.person_name
FROM Queue q1
JOIN Queue q2
  ON q1.turn >= q2.turn
GROUP BY q1.turn, q1.person_name
HAVING SUM(q2.weight) <= 1000
ORDER BY SUM(q2.weight) DESC
LIMIT 1;

7. Complete SQL Query & Execution Flow

Here is the final, clean production query:

SELECT q1.person_name
FROM Queue q1
INNER JOIN Queue q2
  ON q1.turn >= q2.turn
GROUP BY q1.turn, q1.person_name
HAVING SUM(q2.weight) <= 1000
ORDER BY SUM(q2.weight) DESC
LIMIT 1;

Complete Execution Flow Walkthrough

Summary and Key Takeaways

• Problem Objective: Find the exact threshold entity in a sequential queue where a cumulative resource limit (1000 kg) is reached without being exceeded.
• Self-Join Strategy: Joining a table to itself (q1.turn >= q2.turn) is a powerful SQL pattern used to simulate running totals and cumulative windows.
• Aggregation with GROUP BY: Grouping by the primary identifier (q1.turn or q1.person_name) allows us to aggregate historical rows per individual.
• HAVING vs WHERE: Use HAVING when filtering datasets based on aggregate functions like SUM(), COUNT(), or AVG().
• Sorting for Top-N Results: Combining ORDER BY ... DESC with LIMIT 1 isolates the maximum threshold boundary (the last person who fit).
• Incremental Debugging: When writing complex SQL joins, selecting SELECT * first and executing intermediate steps helps visualize how rows pair together before applying aggregate functions.