Solving the Gaps and Islands Problem in SQL

The "Gaps and Islands" problem is a classic SQL puzzle that comes up frequently in real-world scenarios. It involves analyzing a sequence of data to find:

• Islands: Consecutive ranges of values (e.g., a user logging in 5 days in a row).
• Gaps: Missing values in a sequence (e.g., finding available appointment slots in a schedule).

Despite being a common problem, the solution isn't always intuitive. In this post, we'll explore the "Row Number Difference" technique, which is one of the most elegant ways to solve this.

A Real Business Scenario: Streaks, Downtime, and Missing Coverage

Gaps-and-islands is famous as an interview pattern, but it matters because many operational questions are really sequence questions:

• how many days in a row was a customer active
• where are the missing invoice numbers in a regulated process
• how long did a machine run before the next outage
• which appointment slots remain open between booked times

The point is not the puzzle. The point is identifying boundaries between consecutive runs and breaks in a sequence.

The Scenario: Login Streaks

Imagine a table tracking user login dates. We want to find "Islands" of activity—consecutive days where a user logged in—to reward them for streaks.

User	Login Date
Alice	2024-01-01
Alice	2024-01-02
Alice	2024-01-03
Alice	2024-01-05
Alice	2024-01-06

Here, Alice has two streaks (islands):

1. Jan 1 to Jan 3 (3 days)
2. Jan 5 to Jan 6 (2 days) Jan 4 is a "gap".

The Solution: Row Number Difference

The core insight is this: If a sequence is consecutive, the difference between the value and its rank (row number) will be constant.

Let's verify this mathematically. If we assign a ROW_NUMBER() to the dates:

Date (D)	Row Num (RN)	D - RN
Jan 1	1	Jan 0
Jan 2	2	Jan 0
Jan 3	3	Jan 0
Jan 5	4	Jan 1
Jan 6	5	Jan 1

Notice how D - RN is constant ("Jan 0") for the first group, and then changes to "Jan 1" for the second group. This "group identifier" allows us to group consecutive rows together!

A Common Mistake: Forgetting That "Consecutive" Depends on the Grain

This pattern only works when the sequence rule is defined correctly.

That sounds obvious, but it causes real mistakes:

• treating calendar days as consecutive when the business only counts business days
• applying the pattern to timestamps when the intended grain is sessions or dates
• forgetting to deduplicate same-day events before looking for login streaks
• ranking across all users instead of partitioning by entity

The row-number trick is elegant, but it is only as correct as the sequence definition underneath it.

Constructing the Query

1. Generate Row Numbers: Order by date for each user.
2. Calculate the Group ID: Subtract the row number (converted to days) from the login date.
3. Group By the Difference: Aggregate to find the start and end of each streak.

WITH RankedLogs AS (
    SELECT
        username,
        login_date,
        ROW_NUMBER() OVER (PARTITION BY username ORDER BY login_date) as rn
    FROM user_logins
),
GroupedLogs AS (
    SELECT
        username,
        login_date,
        -- Subtract RN days from login_date to get the 'Island ID'
        date(login_date, '-' || rn || ' days') as island_id
    FROM RankedLogs
)
SELECT
    username,
    MIN(login_date) as streak_start,
    MAX(login_date) as streak_end,
    COUNT(*) as streak_length
FROM GroupedLogs
GROUP BY username, island_id
ORDER BY username, streak_start;

Interactive Gaps & Islands Playground

Try it yourself! In this example, we look for "Islands" of consecutive manufacturing serial numbers to see batches.

Finding Gaps

Finding what's missing is just as important. To find gaps, you usually use LEAD() to look at the next value and check if it's more than 1 unit away.

SELECT
    serial_number + 1 as gap_start,
    next_serial - 1 as gap_end
FROM (
    SELECT
        serial_number,
        LEAD(serial_number) OVER (ORDER BY serial_number) as next_serial
    FROM manufacturing_log_gaps
) sub
WHERE next_serial - serial_number > 1;

Boundary and Performance Notes

Sequence analysis is compact in SQL, but a few details matter a lot:

• duplicates can break the grouping logic unless you collapse to the intended grain first
• date arithmetic differs by database dialect, especially once timestamps and intervals are involved
• large partitions need sorting for ROW_NUMBER() and LEAD(), so indexing and pre-filtering still matter
• integer sequences are simpler than time sequences, where weekends, holidays, and missing expected periods may change the definition of a gap

Before optimizing, confirm the rule for consecutiveness. That is usually the hardest part of the problem.

When NOT to Use the Row-Number Difference Pattern

Avoid forcing this exact technique when:

• the islands are defined by variable time thresholds rather than exact adjacency
• the grouping rule depends on attributes beyond order, such as status changes or session timeouts
• the data has overlapping ranges rather than discrete points
• a calendar table or interval-join approach expresses the logic more directly

Gaps-and-islands is a family of problems, not one universal query template.

Official References

• PostgreSQL window function documentation for ROW_NUMBER, LEAD, and related ordered-row functions.
• PostgreSQL date/time functions for the date arithmetic often used in streak analysis.
• SQLite window functions documentation for the SQLite support used in browser-playground friendly versions of this pattern.

Conclusion

The row-number difference method is powerful because it turns a messy sequence question into a stable grouping key. Once you trust the grain and the definition of "consecutive," the pattern becomes useful for streaks, missing ranges, and operational continuity checks across many domains.

Related Articles

• Mastering SQL LEAD and LAG Functions for Row Comparisons for the neighboring-row functions that often appear alongside gap detection.
• Sessionization: Grouping Events into User Sessions in SQL for a practical event-analytics case where boundary detection defines groups.
• Understanding Window Functions: A Practical Guide for the broader mental model behind row-number and lead/lag based solutions.