DEV Community

Cover image for Solving the Classic SQL "Gaps and Islands" Problem: 3 Modern Approaches
Rahman
Rahman

Posted on AI-assisted

Solving the Classic SQL "Gaps and Islands" Problem: 3 Modern Approaches

If you've ever needed to find consecutive streaks in data — days a user logged in back to back, uninterrupted stretches of sensor readings, runs of matching status codes — you've run into the "gaps and islands" problem. The "islands" are the consecutive runs. The "gaps" are the breaks between them. SQL doesn't have a built-in FIND_STREAKS() function, so you build it with window functions instead.

Here's the sample data we'll use throughout — a table of user login dates:

user_id login_date
1 2026-01-01
1 2026-01-02
1 2026-01-03
1 2026-01-05
1 2026-01-06

User 1 logged in three days straight, skipped the 4th, then logged in two more days. That's two islands — a 3-day streak and a 2-day streak — separated by one gap. Every approach below should output exactly that:

user_id streak_start streak_end streak_length
1 2026-01-01 2026-01-03 3
1 2026-01-05 2026-01-06 2

Quick refresher: the window functions doing the work

Before the approaches, three building blocks, briefly:

  • ROW_NUMBER() OVER (PARTITION BY ... ORDER BY ...) — numbers rows 1, 2, 3... within each group, in the order you specify. Doesn't skip numbers, doesn't care about ties.
  • LAG(col) OVER (...) — looks at the previous row's value for that column, for the current row. LEAD() is the same idea but looks forward instead.
  • SUM(col) OVER (PARTITION BY ... ORDER BY ...) — a running total, recalculated row by row, instead of collapsing everything into one number the way a normal SUM() in a GROUP BY would.

All three approaches below are really just different combinations of these three ideas.

Approach 1: The row-number trick

This is the classic, and the cleverest one to understand. Here's the logic: if a run of dates has zero gaps, then subtracting a simple counter (1, 2, 3...) from each date should always land on the same result — because both the dates and the counter are increasing by exactly one each row. The moment there's a gap, that arithmetic breaks, and the result shifts to a new value. That shift is exactly what makes it usable as a group ID — rows in the same island always land on the same computed value, and rows in a different island always land on a different one.

WITH numbered AS (
  SELECT
    user_id,
    login_date,
    ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY login_date) AS rn
  FROM login_days
)
SELECT
  user_id,
  MIN(login_date) AS streak_start,
  MAX(login_date) AS streak_end,
  COUNT(*) AS streak_length
FROM numbered
GROUP BY user_id, login_date - (rn * INTERVAL '1 day')
ORDER BY user_id, streak_start;
Enter fullscreen mode Exit fullscreen mode

Walking through it: rn gives each row a position (1, 2, 3, 4, 5). Subtracting rn days from login_date gives Jan 1, Jan 1, Jan 1, Jan 2, Jan 2 — the first three rows collapse to the same value because there's no gap between them, and the last two collapse to a different shared value because the gap on Jan 4 threw the counter out of sync. Group by that computed value, and each group is one island.

It's elegant once it clicks, but it only works cleanly for evenly-spaced values like whole days or plain integers. Try it on timestamps or irregular intervals and the subtraction stops producing clean matches.

Approach 2: Flag-then-sum

More flexible, and easier to explain to a teammate six months from now, because every step is visible instead of relying on one clever subtraction. First, compare each row to the one before it using LAG(), and flag it with a 1 whenever there's a gap — meaning this row starts a brand new island. Then run a cumulative SUM() over that flag. Since the flag only increases when a new island starts, that running total is the island number — it stays flat across a streak and steps up by one every time a new streak begins.

WITH flagged AS (
  SELECT
    user_id,
    login_date,
    CASE
      WHEN login_date - LAG(login_date) OVER (PARTITION BY user_id ORDER BY login_date) = 1
      THEN 0 ELSE 1
    END AS is_new_streak
  FROM login_days
)
SELECT
  user_id,
  MIN(login_date) AS streak_start,
  MAX(login_date) AS streak_end,
  COUNT(*) AS streak_length
FROM (
  SELECT *, SUM(is_new_streak) OVER (PARTITION BY user_id ORDER BY login_date) AS streak_id
  FROM flagged
) grouped
GROUP BY user_id, streak_id
ORDER BY user_id, streak_start;
Enter fullscreen mode Exit fullscreen mode

Notice the is_new_streak flag is a single CASE expression you fully control. Right now it checks "is the gap more than 1 day," but you could just as easily change the condition to "is the gap more than 1 hour," or "did the status code change," and the rest of the query wouldn't need to change at all. That's what makes this the one worth reaching for by default.

Approach 3: Match the boundaries directly

No grouping, no aggregation step — just find every row where a streak starts (the day before it is missing from the data) and every row where a streak ends (the day after it is missing), then line up the Nth start with the Nth end.

WITH boundaries AS (
  SELECT
    user_id,
    login_date,
    CASE WHEN LAG(login_date) OVER (PARTITION BY user_id ORDER BY login_date) = login_date - 1 THEN 0 ELSE 1 END AS is_start,
    CASE WHEN LEAD(login_date) OVER (PARTITION BY user_id ORDER BY login_date) = login_date + 1 THEN 0 ELSE 1 END AS is_end
  FROM login_days
),
starts AS (
  SELECT user_id, login_date AS streak_start,
         ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY login_date) AS rn
  FROM boundaries WHERE is_start = 1
),
ends AS (
  SELECT user_id, login_date AS streak_end,
         ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY login_date) AS rn
  FROM boundaries WHERE is_end = 1
)
SELECT s.user_id, s.streak_start, e.streak_end
FROM starts s
JOIN ends e ON s.user_id = e.user_id AND s.rn = e.rn
ORDER BY s.user_id, s.streak_start;
Enter fullscreen mode Exit fullscreen mode

is_start checks whether the previous row is one day back — if not (or if there is no previous row), this row is the beginning of an island. is_end does the mirror check looking forward. Filtering down to just the start rows and just the end rows gives two short lists — the first start pairs with the first end, the second with the second, and so on, because islands can't overlap or interleave.

This skips the group-by step entirely, which can matter on very large tables where aggregation is the expensive part of the query plan. The tradeoff is it takes a moment longer to read for anyone seeing it for the first time — there's more setup before the payoff.

Which one to reach for

Approach 2 is the safest default — readable, flexible, handles unusual gap definitions without a rewrite, and reads almost like plain English once you know what LAG and the running SUM() are doing. Reach for Approach 1 when your data is simple integers or daily dates and you want the shortest possible query, and you're confident nobody will need to change the gap logic later. Reach for Approach 3 when you're working at a scale where skipping the aggregation step actually shows up in your query time — profile first, don't guess.

All three lean on the same two window-function ideas: comparing a row to its neighbor, and turning that comparison into a group. Once that clicks, gaps and islands stops being a "classic hard problem" and starts being a five-minute pattern you reach for on autopilot.

Top comments (2)

Collapse
 
raknaos profile image
Raknaos

Approach 3 is the one I reach for when the grouping step genuinely hurts, but it has a failure mode worth writing down: pairing the nth start with the nth end assumes the two lists are strictly interleaved per partition. The moment a user has a duplicated day — a backfilled row, a double-clocked login — the counts diverge and start #3 silently pairs with end #4. I add a guard comparing the two counts before trusting the result.

On the subtraction trick: it stays clean while the column is a date; the first time it is a timestamptz the arithmetic yields intervals and the grouping collapses. Do you normalise to a date in an up-front CTE, or is that part of why you call approach 1 the fragile one? Which of the three has survived contact with an analyst team that edits the query six months later?

Collapse
 
rahmanfrr profile image
Rahman

Fair catch on the duplicate-day case — adding a COUNT(*) guard between the two CTEs is cheap insurance against a silent mispair.
On timestamps: yeah, DATE(login_date) in the first CTE. That hidden assumption is exactly why I call Approach 1 fragile.
And Approach 2 survives six months out, hands down — "consecutive" always ends up needing a redefinition, and that's a one-line edit there, not a rewrite.