✏️ Explanatory Question

The "gaps and islands" problem — find consecutive streaks of daily activity

👁 6 Views
📘 Detailed Answer
🟢 Easy
← Previous Write a query to calculate a running total (cumulative sum) of daily sales
💡

Answer with Explanation

95

The "gaps and islands" problem — find consecutive streaks of daily activity

Level: Hard — Notoriously tricky; the "difference of two sequences" trick is the elegant senior-level solution.

Scenario: A fitness app wants each user's login streaks — groups of consecutive days they logged in ("islands"), separated by days they missed ("gaps"). For a "30-day streak" badge, you must identify each continuous run and its length. How do you group consecutive dates in SQL?

Sample Data — user_logins (user 1)

login_dateNote
2026-01-01Island 1 (3-day streak)
2026-01-02
2026-01-03
2026-01-06Island 2 (2-day streak) — gap on 4th & 5th
2026-01-07
2026-01-10Island 3 (1-day streak)
The famous trick: For consecutive dates, (date − ROW_NUMBER) stays constant within a streak. As dates increase by 1 and the row number also increases by 1, their difference is unchanged — until a gap breaks it. That constant difference becomes the group key for each island.

How the Trick Works

login_dateROW_NUMBER (rn)date − rn daysGroup
2026-01-0112025-12-31A
2026-01-0222025-12-31A
2026-01-0332025-12-31A
2026-01-0642026-01-02B
2026-01-0752026-01-02B
2026-01-1062026-01-04C

Rows with the same "date − rn" value belong to the same consecutive streak.

Solution — Islands (Consecutive Streaks)

SELECT
    MIN(login_date)                       AS streak_start,
    MAX(login_date)                       AS streak_end,
    COUNT(*)                              AS streak_length
FROM (
    SELECT
        login_date,
        -- subtract the row-number (in days) to get a constant group key
        DATE_SUB(
            login_date,
            INTERVAL ROW_NUMBER() OVER (ORDER BY login_date) DAY
        ) AS grp
    FROM user_logins
    WHERE user_id = 1
) t
GROUP BY grp
ORDER BY streak_start;
streak_startstreak_endstreak_length
2026-01-012026-01-033
2026-01-062026-01-072
2026-01-102026-01-101

Bonus — Finding the GAPS (missing ranges)

-- Use LEAD() to find where the next login jumps more than 1 day
SELECT
    DATE_ADD(login_date, INTERVAL 1 DAY)      AS gap_start,
    DATE_SUB(next_login, INTERVAL 1 DAY)      AS gap_end
FROM (
    SELECT login_date,
           LEAD(login_date) OVER (ORDER BY login_date) AS next_login
    FROM user_logins
    WHERE user_id = 1
) t
WHERE DATEDIFF(next_login, login_date) > 1;   -- a gap exists
-- Gap: 2026-01-04 to 2026-01-05, and 2026-01-08 to 2026-01-09
For integer sequences (e.g., order numbers instead of dates), it's even simpler: the group key is just value − ROW_NUMBER() with no date arithmetic. The same "difference of two monotonic sequences" idea applies.
Interviewer follow-up: "Now find each user's LONGEST streak across the whole table." → Wrap the islands query with PARTITION BY user_id in the ROW_NUMBER, then GROUP BY user_id, grp, and finally take MAX(streak_length) per user — the gaps-and-islands pattern scales cleanly with partitioning.
← Previous Write a query to calculate a running total (cumulative sum) of daily sales