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.
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.
- Deduplicate user/day.
- Number days in ascending order per user.
- Group on day_no-row_number.
- 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?