Solving Gaps and Islands with Sequence Correlation

Snippet

Solving Gaps and Islands with Sequence Correlation

The 'Gaps and Islands' problem involves finding contiguous sequences in data. By subtracting a monotonically increasing row number from a sorted sequence of values, all members of a continuous 'island' will result in the same constant value ('grp'). This constant can then be used to group and find the boundaries of each sequence.

snippet.sql
sql
SELECT grp, MIN(val) AS start_range, MAX(val) AS end_range 
FROM (
    SELECT val, val - ROW_NUMBER() OVER(ORDER BY val) AS grp 
    FROM sequences
) t 
GROUP BY grp;

Breakdown

ROW_NUMBER() OVER(ORDER BY val)

Generates a continuous integer sequence based on the sorted values.

val - ROW_NUMBER() ... AS grp

Creates a constant identifier for contiguous values in the sequence.

SELECT grp, MIN(val), MAX(val) ... GROUP BY grp

Aggregates the groups to find the start and end of each contiguous range.

Previous snippet Next snippet

From your library

Solving Gaps and Islands with Sequence Correlation

Related