Recap — The Gaps and Islands Pattern

# The Gaps and Islands Pattern Setup: a user logs in on these dates: Jan 1, 2, 3, 5, 6, 9. What's their longest consecutive-day streak? Answer: 3 days (Jan 1-3). The technique to find this in SQL is called "gaps and islands" — it has a name because it appears so often. ## The trick For each row, compute `date - ROW_NUMBER() OVER (ORDER BY date)`. Consecutive dates produce the same value: | login_date | row_num | date - row_num | |---|---|---| | Jan 1 | 1 | Dec 31 | | Jan 2 | 2 | Dec 31 | | Jan 3 | 3 | Dec 31 | | Jan 5 | 4 | Jan 1 | | Jan 6 | 5 | Jan 1 | | Jan 9 | 6 | Jan 3 | Rows with the same `date - row_num` form an "island" — a consecutive run. Now GROUP BY that value: ```sql WITH numbered AS ( SELECT user_id, login_date, login_date - INTERVAL '1 day' * ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY login_date) AS island_id FROM logins ) 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, island_id ORDER BY user_id, streak_start; ``` Each row in the output is one streak. ## Longest streak per user Wrap and use `ROW_NUMBER` again: ```sql WITH streaks AS ( -- same as above ), ranked AS ( SELECT *, ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY streak_length DESC) AS rnk FROM streaks ) SELECT user_id, streak_start, streak_end, streak_length FROM ranked WHERE rnk = 1; ``` ## Session detection — when "consecutive" is "within N minutes" Same pattern with a different definition of island boundary. Use LAG to find boundaries, then a cumulative SUM to give each island an id. ```sql WITH gapped AS ( SELECT user_id, event_time, CASE WHEN event_time - LAG(event_time) OVER (PARTITION BY user_id ORDER BY event_time) > INTERVAL '30 minutes' THEN 1 ELSE 0 END AS is_new_session FROM events ), sessioned AS ( SELECT user_id, event_time, SUM(is_new_session) OVER (PARTITION BY user_id ORDER BY event_time) AS session_id FROM gapped ) SELECT user_id, session_id, MIN(event_time) AS session_start, MAX(event_time) AS session_end, COUNT(*) AS event_count FROM sessioned GROUP BY user_id, session_id; ``` This is the standard "session by inactivity threshold" pattern. Most product analytics tools (Mixpanel, Amplitude) implement it exactly this way under the hood. ## Other gaps-and-islands questions - **Detecting contract gaps** — "find customers whose contracts had a gap of more than 30 days" → islands of contiguous-enough contracts, then check the gap between islands. - **Counting status transitions** — "how many times did a ticket go from open → closed → reopened" → islands of same-status, then count islands. - **Run-length encoding** — describing time series compactly. All the same trick: identify the boundaries, give every run an id, group. ## Common interview wrong answers 1. **Self-join + correlated subquery** — works but O(n²). Window functions are O(n log n). 2. **Computing all pairwise gaps** — overcomplicated; you only need adjacent gaps. 3. **Using LAG without LAG-aware logic** — LAG alone tells you the previous row but doesn't directly give you islands. ## Takeaway When you see "consecutive", "streak", "session", or "contiguous", think gaps-and-islands. The `date - ROW_NUMBER()` or `SUM(boundary_flag) OVER (...)` patterns cover almost every variant.