medium Last Person to Fit in the Elevator

Because every weight is positive, the prefix sums taken in boarding order can only climb, never dip — so the running total is a monotonically non-decreasing sequence, and the single largest value that is still <= 800 belongs to exactly the last person the elevator can hold before it tips over capacity. That one fact is the whole problem: order by position, accumulate, then pick the biggest cumulative weight under the cap.

Problem in one breath

Table ElevatorQueue(person_id, name, weight, position). People board in position order (1 first). The car holds 800 kg. Return the name of the last person who fits before the cumulative weight would exceed 800. The first person always fits.

The query

WITH cumulative AS (
    SELECT name,
           weight,
           SUM(weight) OVER (ORDER BY position) AS total_weight
    FROM ElevatorQueue
)
SELECT name
FROM cumulative
WHERE total_weight <= 800
ORDER BY total_weight DESC
LIMIT 1;

Three moving parts, and each one earns its place:

• SUM(weight) OVER (ORDER BY position) turns each row into a prefix sum — the total weight of everyone from position 1 up to and including this person.
• WHERE total_weight <= 800 keeps only the prefixes that still fit.
• ORDER BY total_weight DESC LIMIT 1 grabs the deepest surviving prefix — equivalently, the last person who fit.

Why "largest qualifying total" = "last person who fit"

This is the step the naive write-up skips, and it is the actual idea. Sort the rows by position. The prefix sum at position k is w1 + w2 + ... + wk. Adding position k+1 adds w(k+1), which is > 0, so the sequence of totals is strictly increasing:

total(1) < total(2) < total(3) < ... < total(n)

A strictly increasing sequence crosses the 800 line exactly once and never comes back. Everyone before the crossing has a total <= 800; everyone at or after it has a total > 800. So among the qualifying rows, the one with the maximum total is the row sitting immediately to the left of that crossing — and because the sequence is ordered by position, that row's position is the deepest into the queue. "Biggest total under the cap" and "furthest along the queue" are the same row. That is why ORDER BY total_weight DESC LIMIT 1 is allowed to forget about position entirely once the prefix sums exist.

If two weights could be zero or negative the monotonicity breaks and this trick is unsafe — see Pitfalls.

Worked trace

Input (shown in queue / position order, not person_id order):

The WHERE total_weight <= 800 survivors are Alice (200), Charlie (500), Eve (675). ORDER BY total_weight DESC LIMIT 1 picks the max of those, 675 → Eve. Bob is the person who breaks the cap (675 + 150 = 825), so Eve is the last one in.

The default window frame — the real conceptual content

SUM(weight) OVER (ORDER BY position) looks like it just "sums in order," but a window function always computes over a frame: a sliding subset of rows relative to the current row. When you write ORDER BY but omit an explicit frame, SQL substitutes a default, and the default is not "all preceding rows by row count." It is:

RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW

Read literally: sum every row from the start of the partition up to and including every row that is a peer of the current row in the ORDER BY. A peer is a row with the same position value. Here position is unique (the prompt guarantees 1..n), so each row is its own only peer and RANGE behaves identically to a row-by-row prefix sum. That is the only reason the query is correct as written.

The instant the ORDER BY column has duplicates, RANGE bites: all tied rows receive the same cumulative total — the sum through the end of the tie group — not a distinct partial sum each. If you actually wanted each row to add to its predecessor regardless of ties, you must say so explicitly:

SUM(weight) OVER (ORDER BY position
                  ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)

ROWS counts physical rows; RANGE counts value ranges and collapses peers. For monotonic-prefix problems like this elevator, reach for ROWS by habit so a future non-unique sort key cannot silently change your totals.

Pitfalls

• Forgetting the default frame is RANGE, not ROWS. Correct here only because position is unique. Copy this pattern onto a sort key with ties (e.g. ORDER BY order_date with many rows per day) and every tied row gets the tie-group's grand total, silently corrupting your running balance. Default to ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW.
• Ordering the outer query by the wrong column. ORDER BY position DESC LIMIT 1 after the filter does not work in general — it returns whoever happens to sit at the highest qualifying position, but with monotonic prefix sums the highest qualifying total and the highest qualifying position coincide, so it happens to match. Order by total_weight DESC to express the actual intent ("fullest elevator under the cap").
• Negative or zero weights. The whole "max qualifying total = last to fit" argument relies on strictly increasing prefixes. If weights can be ≤ 0 the prefix sum can dip back under 800 after crossing it, and ORDER BY total_weight DESC LIMIT 1 may return someone earlier than a later qualifying person. For physical weights this is fine; know the assumption.
• No window functions available (old MySQL < 8.0). You'd fall back to a correlated subquery: SUM(weight) over peers with position <= e.position. It is O(n²) and far slower; prefer the window function on any modern engine.
• Empty result instead of a row. Not a risk here (the prompt guarantees person 1 fits), but if nobody fit, LIMIT 1 returns zero rows — fine for this grader, but wrap in COALESCE/a sentinel if a caller expects exactly one row.

Takeaways

• Positive increments make prefix sums monotonic; that single property collapses "last to fit" into "max cumulative total ≤ cap," letting you drop the ordering column in the outer query.
• SUM(...) OVER (ORDER BY x) with no frame clause means RANGE UNBOUNDED PRECEDING AND CURRENT ROW — it merges peers. Write ROWS explicitly unless your sort key is provably unique.
• The window function builds the running total in one pass (O(n log n) for the sort); the filter + ORDER BY total DESC LIMIT 1 is just argmax over the survivors.

Re-authored and deepened for this guide. Window-frame semantics (default RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW vs. explicit ROWS, and peer collapsing) follow the SQL:2003/2011 standard as implemented in PostgreSQL ("Window Function Calls," PostgreSQL docs §4.2.8 and §3.5) and MySQL 8.0 ("Window Function Frame Specification"). Problem and example values from the LeetCode-style "Last Person to Fit in the Elevator" prompt; running totals (Eve = 675) recomputed and verified against the example table.