0Pricing
SQL Interview Prep · Lesson

Recognizing a Gaps-and-Islands Problem

Identifying the pattern in a word problem and the core grouping insight.

Recognizing a Gaps-and-Islands Problem is a free SQL Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the SQL Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.

The Pattern Interviewers Are Testing

When a senior interviewer asks you to find consecutive runs of something, you are looking at a gaps-and-islands problem. The name comes from a mental picture: rows that belong together form an island, and the breaks between them are gaps.

  • An island is a maximal run of rows that are adjacent by some rule (consecutive integers, consecutive dates, or the same status repeated).
  • A gap is the missing space between two islands.

Recognizing this class instantly is itself a senior signal. Many candidates reach for a tangle of self-joins; the elegant answer is almost always window functions.

Word Problems That Hide an Island

The challenge is that interviewers rarely say "gaps and islands." They disguise it. Train your ear for phrasing like:

  • "Find each period a user was continuously subscribed."
  • "How many consecutive days did the server stay up?"
  • "Which ranges of IDs are missing from this table?"
  • "Collapse adjacent rows with the same status into one row."

Every one of these is the same shape: group rows that are next to each other, then report the start, end, or absence of those groups. Once you map the words to islands, the SQL writes itself.

The Core Insight: Manufacture a Group Key

Here is the whole trick in one sentence: if you can assign every row in the same island an identical group key, then a simple GROUP BY collapses each island into one summary row.

So the real work in any gaps-and-islands problem is computing that group key. Different variants compute it differently, but they all share this goal. Once you have the key, the final step is trivial:

SELECT
  grp,
  MIN(value) AS island_start,
  MAX(value) AS island_end,
  COUNT(*)   AS island_length
FROM rows_with_group_key
GROUP BY grp
ORDER BY island_start;

A Concrete Dataset

Let's anchor on data. Imagine a logins table tracking which day numbers a user logged in:

  • Days present: 1, 2, 3, 7, 8, 10

By eye, the islands are {1,2,3}, {7,8}, and {10}. The gaps are days 4-6 and day 9. Your job in an interview is to make the database see these three islands without you pointing them out manually. Keep this tiny dataset in mind as we explore each technique.

CREATE TABLE logins (day_no INT);
INSERT INTO logins VALUES (1),(2),(3),(7),(8),(10);

Why Naive Approaches Fail

A common first instinct is to compare each row to the next with a self-join and flag breaks. That works for finding a single gap but quickly becomes unwieldy:

  • You need to detect both the start and end of each island, which means two passes or two joins.
  • Edge rows (the very first and very last) need special handling.
  • It does not generalize to "give me the length of every run" without more machinery.

Interviewers watch for whether you escalate to a self-join war or recognize that one pass with a window function is cleaner.

The Gap-Detection Mental Model

One robust framing is: a new island starts whenever the current row is not adjacent to the previous row. Use LAG to look back one row and compare.

If day_no - LAG(day_no) is greater than 1 (or NULL for the first row), this row begins a new island. We mark that with a flag of 1, otherwise 0. Watch what those flags look like for our data.

SELECT
  day_no,
  CASE
    WHEN day_no - LAG(day_no) OVER (ORDER BY day_no) = 1 THEN 0
    ELSE 1
  END AS is_new_island
FROM logins
ORDER BY day_no;

Turning Flags Into a Group Key

The flags from the previous step are 1, 0, 0, 1, 0, 1 for days 1,2,3,7,8,10. Notice that a running sum of those flags produces a number that stays constant within an island and increments at each new island: 1,1,1,2,2,3.

That running sum is our manufactured group key. We wrap the flag query in a CTE and sum it with another window function:

WITH flagged AS (
  SELECT
    day_no,
    CASE WHEN day_no - LAG(day_no) OVER (ORDER BY day_no) = 1
         THEN 0 ELSE 1 END AS is_new_island
  FROM logins
)
SELECT
  day_no,
  SUM(is_new_island) OVER (ORDER BY day_no) AS grp
FROM flagged;

Completing the Worked Example

Now stack the final GROUP BY on top of the group key. Each distinct grp value is one island, and we report its boundaries and size:

The result is exactly the three islands we spotted by eye: 1-3 (length 3), 7-8 (length 2), and 10-10 (length 1). This three-layer recipe (flag, running sum, group) is the backbone of nearly every gaps-and-islands answer you will write.

WITH flagged AS (
  SELECT day_no,
    CASE WHEN day_no - LAG(day_no) OVER (ORDER BY day_no) = 1
         THEN 0 ELSE 1 END AS is_new
  FROM logins
),
keyed AS (
  SELECT day_no,
    SUM(is_new) OVER (ORDER BY day_no) AS grp
  FROM flagged
)
SELECT grp, MIN(day_no) AS start_day,
       MAX(day_no) AS end_day, COUNT(*) AS len
FROM keyed GROUP BY grp ORDER BY start_day;

Adjacency Is Domain-Specific

The only part that changes between problems is the definition of adjacent. Recognizing the right adjacency rule is half of recognizing the problem:

  • Integers: adjacent when the difference is exactly 1.
  • Calendar days: adjacent when one date is the next day (date = prev + INTERVAL '1 day').
  • Status periods: adjacent when the status value is unchanged from the previous row.

Same skeleton, different comparison inside the CASE. Spotting which adjacency applies is the clarifying question you should voice aloud in the interview.

Clarifying Questions To Ask

Before writing a line of SQL, score points by clarifying scope. Good gaps-and-islands clarifications:

  • "Should I treat the data per user, or globally?" (That decides whether you add PARTITION BY user_id.)
  • "Can there be duplicate values on the same day, and do they break or extend a run?"
  • "Do you want the islands, the gaps, or both?"
  • "Is the sequence guaranteed sorted, or should I order it myself?"

Voicing these shows you have solved this class before and understand its edge cases.

Per-Group Islands With PARTITION BY

Real interview data is almost always grouped, for example logins per user. The fix is mechanical: add PARTITION BY user_id to every window function so islands never span across users.

The skeleton is identical; you just partition. This is why mastering the single-stream case first pays off, because scaling to per-group is a one-clause change.

SELECT
  user_id, day_no,
  CASE WHEN day_no - LAG(day_no)
         OVER (PARTITION BY user_id ORDER BY day_no) = 1
       THEN 0 ELSE 1 END AS is_new
FROM logins;

Quick Check

Test your pattern-recognition instinct.

Recap: Spotting the Shape

You can now identify a gaps-and-islands problem from its disguise and name the strategy:

  • Trigger words: consecutive, continuous, unbroken, streak, missing ranges, collapse adjacent.
  • Core idea: assign every row in the same run one identical group key, then GROUP BY it.
  • Recipe: flag new islands with LAG, running-sum the flags into a key, then aggregate.
  • Adjacency is domain-specific (integers, dates, or unchanged status).
  • Add PARTITION BY for per-group analysis; clarify scope before coding.

Next we sharpen the most elegant key-building method: the row-number difference trick.

Frequently asked questions

Is the “Recognizing a Gaps-and-Islands Problem” lesson free?

Yes — the full text of “Recognizing a Gaps-and-Islands Problem” is free to read here on the web, and the SQL Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the SQL Interview Prep course, upgrade to CoddyKit PRO.

What will I learn in “Recognizing a Gaps-and-Islands Problem”?

Identifying the pattern in a word problem and the core grouping insight. You practise SQL Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.

Do I need any experience to start SQL Interview Prep?

No prior experience is required. SQL Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.

How long does the “Recognizing a Gaps-and-Islands Problem” lesson take?

Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.

Can I write and run code in this SQL Interview Prep lesson?

Yes. Every SQL Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.

All lessons in this course

  1. Recognizing a Gaps-and-Islands Problem
  2. The Row-Number Difference Trick
  3. Finding Gaps in a Sequence
  4. Islands With Date and Status Changes
← Back to SQL Interview Prep