LeetCode 1204 - Last Person to Fit in the Bus

This problem gives us a database table named Queue that represents people waiting to board a bus. Each row contains a person's ID, name, weight, and boarding order. The turn column determines the exact sequence in which people attempt to board the bus.

leetcodemediumdatabase

LeetCode Problem 1204

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem gives us a database table named Queue that represents people waiting to board a bus. Each row contains a person's ID, name, weight, and boarding order. The turn column determines the exact sequence in which people attempt to board the bus.

The bus has a strict weight limit of 1000 kilograms. People board one at a time, in increasing order of turn. As soon as adding another person would cause the total weight to exceed 1000, that person cannot board, and nobody after them boards either because boarding happens sequentially.

The task is to determine the name of the last person who successfully boards the bus without violating the weight limit.

The important detail is that we are not asked to return all passengers who fit. Instead, we only need the final person whose inclusion still keeps the cumulative weight at or below 1000.

The input table represents:

Column Meaning
person_id Unique identifier for each person
person_name Name of the passenger
weight Passenger weight in kilograms
turn Boarding order

The expected output is a single row containing the person_name of the last valid passenger.

The constraints tell us several useful things about the structure of the input:

  • turn values are unique and range from 1 to n
  • Boarding order is completely deterministic
  • The first passenger is guaranteed to fit
  • Only cumulative weight matters

This is fundamentally a running total problem. We need to process rows in order and continuously compute the sum of weights.

Several edge cases are important:

  • The total weight may reach exactly 1000, which is still valid
  • Only the first passenger may fit
  • Every passenger may fit
  • The person who exceeds the limit should not be included
  • Ordering by turn is critical, processing rows in arbitrary order gives incorrect results

Approaches

Brute Force Approach

A straightforward approach is to simulate the boarding process manually.

We first sort all people by their turn. Then, for every person, we compute the cumulative weight of all passengers from the beginning up to that person. If the cumulative weight remains less than or equal to 1000, that passenger is currently the last valid passenger. Once the total exceeds 1000, we stop.

In SQL, a naive brute force solution could repeatedly compute sums using correlated subqueries. For each row, we calculate the total weight of all rows with turn less than or equal to the current row's turn.

This approach is correct because it directly models the boarding process exactly as described in the problem. However, repeatedly recomputing sums for each row is inefficient.

Optimal Approach

The key insight is that this is a cumulative sum, or running total, problem.

Instead of recomputing totals repeatedly, we can use a SQL window function to calculate the running weight efficiently in a single pass over the ordered rows.

Using:

SUM(weight) OVER (ORDER BY turn)

we can compute the cumulative bus weight after each passenger boards.

Once we have the running totals, we simply filter rows where the cumulative weight is less than or equal to 1000, then select the passenger with the largest turn.

This approach is efficient, concise, and maps naturally to the problem requirements.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Recomputes cumulative sums repeatedly
Optimal O(n log n) O(n) Uses window functions for running totals

The O(n log n) factor comes from ordering by turn, although many database engines may optimize this further if indexing exists.

Algorithm Walkthrough

  1. Sort all passengers by their turn value because boarding must happen in the exact queue order.
  2. Compute a running total of passenger weights using a window function. For each row, calculate the sum of all weights from the beginning of the queue up to the current passenger.
  3. Keep only passengers whose cumulative weight is less than or equal to 1000. These are the passengers who can successfully board the bus.
  4. Among all valid passengers, select the one with the largest turn value because they boarded last.
  5. Return that passenger's person_name.

Why it works

The running sum after processing passenger i exactly represents the total bus weight after that passenger boards. If the running total is less than or equal to 1000, that passenger can board legally. The last such passenger is therefore the final passenger who fits on the bus. Since passengers board strictly in order, no later passenger can board once the limit is exceeded.

Python Solution

Although this is a SQL database problem, we can still demonstrate the logic in Python for algorithmic understanding.

from typing import List

class Solution:
    def lastPersonToFit(self, queue: List[List]) -> str:
        queue.sort(key=lambda person: person[3])

        current_weight = 0
        last_person = ""

        for person_id, person_name, weight, turn in queue:
            if current_weight + weight > 1000:
                break

            current_weight += weight
            last_person = person_name

        return last_person

The implementation begins by sorting passengers according to their boarding order using the turn field. This guarantees we process passengers exactly as the bus boarding sequence requires.

We maintain a variable called current_weight to track the cumulative weight already on the bus. Another variable, last_person, stores the most recent passenger who successfully boarded.

For each passenger, we check whether adding their weight would exceed the bus limit. If so, we stop immediately because no further passengers may board.

Otherwise, we update the cumulative weight and record the current passenger as the latest valid passenger.

At the end, last_person contains the final passenger who fits within the limit.

SQL Solution for LeetCode

SELECT person_name
FROM (
    SELECT
        person_name,
        turn,
        SUM(weight) OVER (ORDER BY turn) AS total_weight
    FROM Queue
) AS running_totals
WHERE total_weight <= 1000
ORDER BY turn DESC
LIMIT 1;

This query first computes cumulative weights using a window function. Then it filters valid boarding states and selects the passenger with the highest turn among them.

Go Solution

package main

import (
	"sort"
)

type Person struct {
	personID   int
	personName string
	weight     int
	turn       int
}

func lastPersonToFit(queue []Person) string {
	sort.Slice(queue, func(i, j int) bool {
		return queue[i].turn < queue[j].turn
	})

	currentWeight := 0
	lastPerson := ""

	for _, person := range queue {
		if currentWeight+person.weight > 1000 {
			break
		}

		currentWeight += person.weight
		lastPerson = person.personName
	}

	return lastPerson
}

The Go implementation follows the same logic as the Python version. We use sort.Slice to order passengers by turn. The cumulative weight is tracked with an integer variable, and we stop processing as soon as the limit would be exceeded.

Go does not have Python style tuple unpacking, so we define a Person struct to store passenger data clearly. Integer overflow is not a concern here because the total weight remains small.

SQL Solution for LeetCode

SELECT person_name
FROM (
    SELECT
        person_name,
        turn,
        SUM(weight) OVER (ORDER BY turn) AS total_weight
    FROM Queue
) AS running_totals
WHERE total_weight <= 1000
ORDER BY turn DESC
LIMIT 1;

Worked Examples

Example 1

Input table:

person_name weight turn
Alice 250 1
Alex 350 2
John Cena 400 3
Marie 200 4
Bob 175 5
Winston 500 6

We process passengers in turn order.

Turn Person Weight Running Total Can Board?
1 Alice 250 250 Yes
2 Alex 350 600 Yes
3 John Cena 400 1000 Yes
4 Marie 200 1200 No

At turn 4, the total exceeds 1000, so Marie cannot board.

The last valid passenger is John Cena.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates the runtime
Space O(1) Only a few variables are used in the simulation

In the SQL solution, the database engine typically performs sorting internally for the window function. The running sum itself is computed efficiently during traversal of the ordered rows.

Test Cases

from typing import List

class Solution:
    def lastPersonToFit(self, queue: List[List]) -> str:
        queue.sort(key=lambda person: person[3])

        current_weight = 0
        last_person = ""

        for person_id, person_name, weight, turn in queue:
            if current_weight + weight > 1000:
                break

            current_weight += weight
            last_person = person_name

        return last_person

solution = Solution()

# Example case
assert solution.lastPersonToFit([
    [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]
]) == "John Cena"  # Standard example

# Only one passenger fits
assert solution.lastPersonToFit([
    [1, "Alice", 1000, 1],
    [2, "Bob", 1, 2]
]) == "Alice"  # Exact limit reached immediately

# Everyone fits
assert solution.lastPersonToFit([
    [1, "Alice", 200, 1],
    [2, "Bob", 300, 2],
    [3, "Charlie", 400, 3]
]) == "Charlie"  # Total is 900

# Exact 1000 at the end
assert solution.lastPersonToFit([
    [1, "A", 300, 1],
    [2, "B", 300, 2],
    [3, "C", 400, 3]
]) == "C"  # Final passenger reaches exactly 1000

# Second passenger exceeds limit
assert solution.lastPersonToFit([
    [1, "A", 900, 1],
    [2, "B", 200, 2]
]) == "A"  # Cannot add second passenger

# Input not initially sorted
assert solution.lastPersonToFit([
    [2, "B", 300, 2],
    [1, "A", 400, 1],
    [3, "C", 200, 3]
]) == "C"  # Sorting by turn is required
Test Why
Standard example Verifies normal cumulative behavior
Only one passenger fits Tests immediate limit exhaustion
Everyone fits Ensures algorithm handles full boarding
Exact 1000 total Confirms equality is allowed
Second passenger exceeds limit Verifies stopping condition
Unsorted input Ensures sorting by turn is necessary

Edge Cases

One important edge case occurs when the cumulative weight becomes exactly 1000. A common mistake is using a strict inequality check such as < 1000 instead of <= 1000. The implementation correctly allows passengers whose addition results in a total weight equal to the limit.

Another critical edge case is when only the first passenger can board. Since the problem guarantees the first passenger always fits, the algorithm must still return that first passenger even if the second passenger immediately exceeds the limit. The implementation handles this naturally because last_person is updated after every successful boarding.

A third edge case involves unsorted input rows. The database table is not guaranteed to be physically ordered by turn. A naive implementation that processes rows in insertion order would produce incorrect results. Both the Python simulation and SQL solution explicitly order by turn, ensuring correctness regardless of input ordering.

A final subtle edge case occurs when every passenger fits within the limit. Some implementations incorrectly stop early or fail to update the final valid passenger. Since the algorithm updates last_person after every successful boarding, the final passenger is returned correctly when the entire queue fits.