Watch 4 video solutions for Report Contiguous Dates, a hard level problem involving Database. This walkthrough by Everyday Data Science has 2,992 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Table: Failed
+--------------+---------+ | Column Name | Type | +--------------+---------+ | fail_date | date | +--------------+---------+ fail_date is the primary key (column with unique values) for this table. This table contains the days of failed tasks.
Table: Succeeded
+--------------+---------+ | Column Name | Type | +--------------+---------+ | success_date | date | +--------------+---------+ success_date is the primary key (column with unique values) for this table. This table contains the days of succeeded tasks.
A system is running one task every day. Every task is independent of the previous tasks. The tasks can fail or succeed.
Write a solution to report the period_state for each continuous interval of days in the period from 2019-01-01 to 2019-12-31.
period_state is 'failed' if tasks in this interval failed or 'succeeded' if tasks in this interval succeeded. Interval of days are retrieved as start_date and end_date.
Return the result table ordered by start_date.
The result format is in the following example.
Example 1:
Input: Failed table: +-------------------+ | fail_date | +-------------------+ | 2018-12-28 | | 2018-12-29 | | 2019-01-04 | | 2019-01-05 | +-------------------+ Succeeded table: +-------------------+ | success_date | +-------------------+ | 2018-12-30 | | 2018-12-31 | | 2019-01-01 | | 2019-01-02 | | 2019-01-03 | | 2019-01-06 | +-------------------+ Output: +--------------+--------------+--------------+ | period_state | start_date | end_date | +--------------+--------------+--------------+ | succeeded | 2019-01-01 | 2019-01-03 | | failed | 2019-01-04 | 2019-01-05 | | succeeded | 2019-01-06 | 2019-01-06 | +--------------+--------------+--------------+ Explanation: The report ignored the system state in 2018 as we care about the system in the period 2019-01-01 to 2019-12-31. From 2019-01-01 to 2019-01-03 all tasks succeeded and the system state was "succeeded". From 2019-01-04 to 2019-01-05 all tasks failed and the system state was "failed". From 2019-01-06 to 2019-01-06 all tasks succeeded and the system state was "succeeded".
Problem Overview: You receive two tables: Succeeded and Failed, each storing dates. The task is to report continuous date ranges in 2019 where the system status stayed the same (either succeeded or failed). Each output row represents a contiguous interval with start_date, end_date, and the corresponding state.
Approach 1: Union + Window Function + Group By (O(n log n) time, O(n) space)
Start by combining both tables into a single dataset using UNION ALL, while attaching a status label ('succeeded' or 'failed'). Filter rows so only dates within 2019 remain. Once merged, sort by date and apply the window function ROW_NUMBER(). The key insight is the classic "gaps and islands" trick: subtract the row number from the date to generate a constant key for consecutive rows belonging to the same state. Rows within the same contiguous sequence produce the same derived value. Group by the state and this derived key, then compute MIN(date) and MAX(date) to form each interval. This approach relies heavily on SQL analytical features and is the most compact way to solve the problem in MySQL.
Approach 2: Window Boundary Detection with LAG (O(n log n) time, O(n) space)
Another way to detect contiguous segments is by comparing each row with the previous row using LAG(). After combining the two tables with UNION ALL, order rows by date and compute the previous date and previous state. A new segment begins when either the state changes or the date is not exactly one day after the previous date. Mark these boundary rows and use a cumulative sum window to assign a group id to each segment. Finally, aggregate each group to produce the start and end dates. This approach makes the segment boundaries explicit and is useful when working with more complex sequence logic using window functions in database queries.
Recommended for interviews: The union + row number grouping method is the expected solution. It demonstrates familiarity with the "gaps and islands" pattern, which frequently appears in SQL interviews. A candidate who explains why date - row_number() creates stable groups for consecutive records shows strong analytical SQL skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Union + ROW_NUMBER() Grouping | O(n log n) | O(n) | Best general solution for contiguous date problems using the gaps-and-islands technique |
| LAG Boundary Detection + Window Grouping | O(n log n) | O(n) | Useful when explicitly detecting state changes or irregular gaps between rows |
