← SQL roadmap

Topic 51 of 52 · Expert

Find consecutive-day login islands

Return each maximal streak as user_id, start_day, end_day, length after deduplicating same-day logins.

ExpertSenior · 5–8 yearsGaps and islands

MySQL 8-compatible SELECT syntax; sample queries also execute in SQLite 3. Window functions require MySQL 8+.

Problem statement

Return each maximal streak as user_id, start_day, end_day, length after deduplicating same-day logins.

Detect retention streaks without counting repeated logins as extra days.

Input: Integer day numbers per user; one day number per calendar day.

Output: Streak ranges ordered by user and start.

  • Day numbers represent consecutive calendar days.
  • Repeated same-day rows are allowed.

Sample 1

Input: user1:1,2,2,3,6
Output: (1,1,3,3),(1,6,6,1)

The duplicate day 2 does not extend the streak.

Sample 2

Input: user2:2,4
Output: (2,2,2,1),(2,4,4,1)

A missing day splits islands.

Brute-force solution

For each day, recursively search predecessor and successor days to find boundaries; repeated work grows with streak length.

O(n log n) for deduplication and ordering.

CREATE TABLE logins(user_id INTEGER, day_no INTEGER);
INSERT INTO logins VALUES(1,1),(1,2),(1,2),(1,3),(1,6),(2,2),(2,4);
WITH d AS (SELECT DISTINCT user_id,day_no FROM logins), r AS (SELECT user_id,day_no,day_no-ROW_NUMBER() OVER(PARTITION BY user_id ORDER BY day_no) island FROM d) SELECT user_id,MIN(day_no) start_day,MAX(day_no) end_day,COUNT(*) length FROM r GROUP BY user_id,island ORDER BY user_id,start_day;
Optimized solution

After deduplication, day_no minus row_number remains constant throughout a consecutive island.

  1. Deduplicate user/day.
  2. Number days in ascending order per user.
  3. Group on day_no-row_number.
  4. Aggregate range and count.
CREATE TABLE logins(user_id INTEGER, day_no INTEGER);
INSERT INTO logins VALUES(1,1),(1,2),(1,2),(1,3),(1,6),(2,2),(2,4);
WITH d AS (SELECT DISTINCT user_id,day_no FROM logins), r AS (SELECT user_id,day_no,day_no-ROW_NUMBER() OVER(PARTITION BY user_id ORDER BY day_no) island FROM d) SELECT user_id,MIN(day_no) start_day,MAX(day_no) end_day,COUNT(*) length FROM r GROUP BY user_id,island ORDER BY user_id,start_day;
Complexity analysis

Time: O(n log n) for deduplication and ordering.

Auxiliary space: O(n) intermediate workspace.

Test cases
  • Repeated logins.
  • Negative day numbers still work.
  • Empty input.
Expected: (1,1,3,3), (1,6,6,1), (2,2,2,1), (2,4,4,1).
Common mistakes
  • Numbering before deduplicating days.
  • Using timestamps with time components as calendar days.
Key takeaways
  • Normalize calendar grain first.
  • Difference-to-position labels islands.
  • Keep partition boundaries.
Follow-up challenges
  • How do time zones change day assignment?
  • How would you retain only streaks of at least three days?
Practise SQL with the AI mentor

Can't find a SQL topic you need for exams or placements? Request it and we'll add it.