Find the gaps

medium~20 min#gaps-and-islands#sql#window-functions

A table events(sequence_no) should contain a contiguous run of integers. Some are missing. Return the ranges of missing values.

Then: how would you find contiguous runs of present values instead?

Solution

Gaps. Compare each row to the next one; where they are not adjacent, the space between is a gap.

WITH s AS (
  SELECT sequence_no,
         LEAD(sequence_no) OVER (ORDER BY sequence_no) AS next_no
    FROM events
)
SELECT sequence_no + 1 AS gap_start,
       next_no - 1     AS gap_end
  FROM s
 WHERE next_no > sequence_no + 1;

Islands — runs of consecutive present values — use the trick worth remembering. Subtract a dense row number from the value:

WITH s AS (
  SELECT sequence_no,
         sequence_no - ROW_NUMBER() OVER (ORDER BY sequence_no) AS grp
    FROM events
)
SELECT MIN(sequence_no) AS run_start, MAX(sequence_no) AS run_end
  FROM s GROUP BY grp ORDER BY run_start;

Why it works. Within a consecutive run, the value and the row number increase together, so their difference is constant. The moment a value is skipped, the value jumps but the row number does not, and the difference changes. That difference is therefore a group key identifying each run — no join, no procedural loop, one pass.

Edge cases to state: duplicates break the row-number trick (use DENSE_RANK, or de-duplicate first), and the query finds only internal gaps — a gap before the first row or after the last needs the expected bounds supplied explicitly.

The follow-up they will ask

The sequence numbers are per user rather than global. What changes?