Human Traffic of Stadium

A monotonically increasing id grows by exactly 1 per row, and so does ROW_NUMBER() over the surviving rows after filtering — so within an unbroken run their difference id - ROW_NUMBER() is a constant, and the instant a row is dropped (a gap) the id leaps ahead of the row number, bumping that constant to a new value. That difference becomes a free group label: same value = same run, and counting rows per label finds runs of length 3 or more.

Problem

Table Stadium(id INT, visit_date DATE, people INT). id is the primary key; as id increases the date increases too. Display every record that is part of a run of three or more consecutive ids where each such row has people >= 100. Return rows ordered by visit_date ascending.

The subtlety: "consecutive" is about the id sequence, but we only care about ids whose row clears the 100 threshold. A single sub-100 day in the middle breaks the run. This is the classic gaps-and-islands problem — islands are the qualifying runs, gaps are where the chain snaps.

The input we will trace

Eight rows. Two of them (id 1 and 4) have people < 100 and will be filtered out before any grouping happens.

Why id - ROW_NUMBER() labels runs — the arithmetic, proven

After the WHERE people >= 100 filter, six rows remain: ids 2, 3, 5, 6, 7, 8. ROW_NUMBER() OVER (ORDER BY id) walks these surviving rows in id order and hands out 1, 2, 3, 4, 5, 6 — a gapless counter, because it only sees the rows that survived, not the original ids. Now subtract, row by row:

The mechanism in one line of algebra: along an unbroken run both id and row_number step up by 1 each row, so their difference cancels and stays flat. At a gap of size k, id leaps forward by k while row_number still only advances by 1, so the difference rises by k−1 — permanently — minting a new label for everything after. Rows 2–3 share label 1; rows 5–8 share label 2. The skipped id 4 is exactly what forced the jump from 1 to 2.

The query

Three stages: filter and label, count per label, keep labels with ≥ 3 rows and pull the real rows back.

WITH ConsecutiveGroups AS (
    -- Stage 1: keep busy days, then label each by id - dense rank
    SELECT
        id,
        visit_date,
        people,
        id - ROW_NUMBER() OVER (ORDER BY id) AS grp
    FROM Stadium
    WHERE people >= 100
),
GroupedCounts AS (
    -- Stage 2: which labels are runs of 3+ ?
    SELECT grp
    FROM ConsecutiveGroups
    GROUP BY grp
    HAVING COUNT(*) >= 3
)
-- Stage 3: pull back the full rows of the qualifying runs
SELECT c.id, c.visit_date, c.people
FROM ConsecutiveGroups c
JOIN GroupedCounts g ON c.grp = g.grp
ORDER BY c.visit_date;

Key ordering fact: the WHERE clause runs before ROW_NUMBER() in the same SELECT, so the window function numbers only the surviving rows. That is the whole reason the row numbers are dense (1..6) while the ids are sparse (2,3,5,6,7,8) — the mismatch is what encodes the gaps.

Tracing the three stages on the real data

Stage 1 — ConsecutiveGroups: the six survivors, each carrying its computed grp (the third column of the arithmetic table above).

id 4 (99 people) never reaches this stage — the filter dropped it, and its absence is precisely what split label 1 from label 2.

Stage 2 — GroupedCounts: count rows per label, keep only counts ≥ 3.

Stage 3 — join back and order: only grp = 2 survives, so we emit ids 5, 6, 7, 8 sorted by visit_date.

Why the obvious approaches fail

The naive self-join. A tempting first attempt is to join the table to itself three times to find rows n, n+1, n+2 all ≥ 100:

-- WRONG for the stated requirement
SELECT DISTINCT a.id, a.visit_date, a.people
FROM Stadium a, Stadium b, Stadium c
WHERE a.people >= 100 AND b.people >= 100 AND c.people >= 100
  AND ( (a.id = b.id-1 AND a.id = c.id-2)   -- a is first of the trio
     OR (a.id = b.id+1 AND a.id = c.id-1)   -- a is middle
     OR (a.id = b.id+2 AND a.id = c.id+1) ) -- a is last
ORDER BY a.visit_date;

This happens to pass on LeetCode because the test asks for runs of exactly 3+, but it is hard-wired to the window size 3: change the requirement to "4 or more" and you must add a fourth join and rewrite every clause. The gaps-and-islands version generalizes by editing one number (HAVING COUNT(*) >= 4). For a long table the triple self-join is also roughly O(n³) work versus a single sort-based pass.

The off-by-one trap with id instead of ROW_NUMBER(). Some learners try to label runs by subtracting from visit_date or by comparing id to a lagged id and reset a counter manually — SQL has no running mutable counter across rows without recursion, so that path leads to a recursive CTE that is far heavier. The id - ROW_NUMBER() trick is the cheap closed-form substitute.

Pitfalls

• Assuming the natural key is gapless. The trick only needs the kept keys to be integers that increase by 1 within a run. If ids themselves can skip even among qualifying rows (e.g. soft-deleted rows leaving holes in the PK), id - ROW_NUMBER() still works because the gap simply forces a new label — but if the "sequence" you group on is a date or a non-integer, you must first project it onto a dense integer rank, or the subtraction is meaningless.
• Ties in the ORDER BY of the window. ROW_NUMBER() needs a deterministic order. Here id is unique so it is safe; if you ever order the window by a non-unique column, two rows can get arbitrary adjacent numbers and split or merge runs unpredictably. Always order the window by something unique.
• Filtering after labeling. If you put WHERE people >= 100 in an outer query after computing ROW_NUMBER() over all rows, the row numbers count the sub-100 rows too, so the difference no longer encodes the qualifying-run gaps. The filter must happen before the window numbers the rows — which is why it lives inside the same CTE as the WHERE.
• Returning the count column. The final SELECT must project the original columns (id, visit_date, people), not grp or group_size. Leaking the helper columns into the result set is a common reason an otherwise-correct query is marked wrong.

Takeaways

• Gaps-and-islands in one idiom: subtract a dense ROW_NUMBER() from a strictly-increasing key; equal differences are one island, a change in the difference marks a gap.
• It works because two synchronized +1 counters cancel. The difference only moves when the key outpaces the row number — i.e. exactly at a gap — so the label is stable for free, no manual state.
• Filter before you number. Whatever defines membership in a run must be applied before the window function, so the gaps you care about are the only gaps the arithmetic sees.
• It generalizes by one parameter. Run length 3, 4, or N is just the HAVING COUNT(*) >= N threshold — no structural rewrite, unlike a self-join chain.

Problem from LeetCode 601 “Human Traffic of Stadium” (Hard). The gaps-and-islands technique — key − ROW_NUMBER() as a run label — is documented in Itzik Ben-Gan, T-SQL Querying (Microsoft Press) and is folklore across the PostgreSQL and SQL Server communities (see Joe Celko, SQL for Smarties, on sequence/island queries). Window-function evaluation order (WHERE before window functions) follows the SQL standard logical processing order, covered in the PostgreSQL documentation, §7.2.5. Re-authored and deepened for this guide: the original page asserted that consecutive ids share a grp without proof — this version proves it with row-by-row subtraction, contrasts a gapped versus ungapped run in a hand-drawn mechanism diagram, and adds the naive-self-join failure mode.