Gap & Island Problems

Advanced SQL

Find Patterns in Sequences

Gap and island problems ask: "What's missing?" and "What's consecutive?" Islands are consecutive sequences; gaps are the spaces between them. The core technique uses ROW_NUMBER() — consecutive values produce the same difference from the row number.

Island Detection — Find consecutive active users, streak days
Gap Detection — Find missing dates, gaps in sequences
Range Merging — Overlap or adjacency-based grouping
Gap Filling — Fill missing dates with interpolated values

This pattern is one of the most common SQL interview questions — it tests whether you can think in sets rather than loops.

The Core Pattern

Classic Gap Problem

-- Find missing dates in a date series
WITH date_range AS (
  SELECT generate_series(
    MIN(sale_date), MAX(sale_date), '1 day'::INTERVAL
  )::DATE AS expected_date
  FROM sales
)
SELECT dr.expected_date AS missing_date
FROM date_range dr
LEFT JOIN sales s ON dr.expected_date = s.sale_date
WHERE s.sale_date IS NULL
ORDER BY dr.expected_date;

Island Detection with ROW_NUMBER

-- Find consecutive days of user activity (streaks)
WITH numbered AS (
  SELECT
    user_id, activity_date,
    activity_date - ROW_NUMBER() OVER (
      PARTITION BY user_id ORDER BY activity_date
    )::INT AS island_id
  FROM user_activity
)
SELECT
  user_id,
  MIN(activity_date) AS streak_start,
  MAX(activity_date) AS streak_end,
  COUNT(*) AS streak_length,
  MAX(activity_date) - MIN(activity_date) + 1 AS days_span
FROM numbered
GROUP BY user_id, island_id
HAVING COUNT(*) >= 3  -- At least 3 consecutive days
ORDER BY user_id, streak_start;

ℹ️

Key Insight: The gap-island pattern uses ROW_NUMBER() to identify consecutive sequences. When you subtract the row number from the value, consecutive values produce the same result, creating "islands." This works for dates, numbers, and any sequential data.

Gap Detection in Sequential Data

-- Find gaps in order sequences
WITH numbered_orders AS (
  SELECT
    order_id, order_date,
    LAG(order_date) OVER (ORDER BY order_date) AS prev_date
  FROM orders
)
SELECT
  prev_date AS gap_end,
  order_date AS gap_start,
  order_date - prev_date - 1 AS gap_days
FROM numbered_orders
WHERE order_date - prev_date > 1
ORDER BY prev_date;

Consecutive Value Islands

-- Find consecutive identical values (same revenue for N days)
WITH numbered AS (
  SELECT
    product_id, sale_date, revenue,
    sale_date - ROW_NUMBER() OVER (
      PARTITION BY product_id ORDER BY sale_date
    )::INT AS island_id
  FROM daily_sales
)
SELECT
  product_id,
  MIN(sale_date) AS period_start,
  MAX(sale_date) AS period_end,
  revenue AS daily_revenue,
  COUNT(*) AS consecutive_days,
  SUM(revenue) AS total_revenue
FROM numbered
GROUP BY product_id, island_id, revenue
HAVING COUNT(*) >= 5
ORDER BY product_id, period_start;

Range-Based Islands (Merging Overlapping Ranges)

-- Group overlapping or adjacent bookings
WITH ordered_ranges AS (
  SELECT room_id, start_time, end_time,
    ROW_NUMBER() OVER (PARTITION BY room_id ORDER BY start_time) AS rn
  FROM bookings
),
merged AS (
  SELECT room_id, start_time, end_time,
    start_time AS group_start, end_time AS group_end
  FROM ordered_ranges WHERE rn = 1

  UNION ALL

  SELECT o.room_id, o.start_time, o.end_time,
    CASE WHEN o.start_time <= m.group_end + INTERVAL '30 minutes'
      THEN m.group_start ELSE o.start_time END,
    CASE WHEN o.end_time > m.group_end
      THEN o.end_time ELSE m.group_end END
  FROM merged m
  INNER JOIN ordered_ranges o ON o.room_id = m.room_id
    AND o.rn = (SELECT MIN(rn) FROM ordered_ranges
                WHERE room_id = m.room_id AND rn > m.rn)
)
SELECT room_id, MIN(group_start), MAX(group_end),
  MAX(group_end) - MIN(group_start) AS total_duration
FROM merged GROUP BY room_id;

Missing Consecutive Numbers

-- Find missing seat numbers (like finding empty seats)
WITH numbered AS (
  SELECT seat_number,
    seat_number - ROW_NUMBER() OVER (ORDER BY seat_number) AS gap_id
  FROM occupied_seats
)
SELECT
  MIN(seat_number) + 1 AS gap_start,
  MAX(seat_number) - 1 AS gap_end,
  MAX(seat_number) - MIN(seat_number) - 1 AS gap_size
FROM numbered
GROUP BY gap_id
HAVING MAX(seat_number) - MIN(seat_number) > 1;

Gap Analysis with Statistics

-- Analyze gap patterns per user
WITH gaps AS (
  SELECT user_id, activity_date,
    LAG(activity_date) OVER (PARTITION BY user_id ORDER BY activity_date) AS prev_activity
  FROM user_activity
)
SELECT
  user_id,
  COUNT(*) AS total_gaps,
  AVG(activity_date - prev_activity) AS avg_gap_days,
  MAX(activity_date - prev_activity) AS max_gap_days,
  STDDEV(activity_date - prev_activity) AS stddev_gap_days
FROM gaps
WHERE prev_activity IS NOT NULL AND activity_date - prev_activity > 1
GROUP BY user_id
HAVING COUNT(*) > 5
ORDER BY avg_gap_days DESC;

Quiz: Test Your Knowledge

Follow-Up Questions

How would you find gaps longer than a specific duration?
What's the most efficient way to fill gaps in a time series?
How do you handle gaps across multiple columns simultaneously?
Explain how to detect overlapping ranges and merge them.
How would you implement a sliding window gap detection?

Key Takeaways

Island detection — value - ROW_NUMBER() produces the same result for consecutive values
Gap detection — LAG() + difference check identifies missing values
Range merging — Recursive CTE for overlapping/adjacent range consolidation
Gap filling — generate_series + LEFT JOIN to fill missing dates
HAVING COUNT(*) >= N — Filter islands by minimum consecutive length
Works for dates AND numbers — The ROW_NUMBER trick is universal for sequential data

Gap & Island Problems — Consecutive Sequences, Missing Data Detection