Wards With Complaint Streaks of Three Days or More
A ward that logs complaints day after day usually has a failing pipe or a blocked drain rather than bad luck.
- Difficulty: Hard
- Topics: Window Functions, Dates
- Dialect: MySQL
- Problem: #91
Problem statement
A ward that logs complaints day after day usually has a failing pipe or a blocked drain rather than bad luck. The city engineer wants every streak of consecutive calendar days on which a ward logged at least one complaint, lasting three days or more. Several complaints on one day count as one day; a day without a complaint ends the streak.
Return ward_no, streak_start, streak_end and streak_days for each such streak, ordered by ward_no, then streak_start.
Tables
Table: complaint_log
| Column | Type |
|---|---|
| complaint_id | int |
| ward_no | int |
| category | varchar |
| logged_on | date |
Primary key: complaint_id.
One row per complaint received at the ward office.
Examples
Example 1
complaint_log
| complaint_id | ward_no | category | logged_on |
|---|---|---|---|
| 1 | 45 | Drainage | 2024-07-01 |
| 2 | 45 | Drainage | 2024-07-02 |
| 3 | 45 | Garbage | 2024-07-02 |
| 4 | 45 | Drainage | 2024-07-03 |
| 5 | 45 | Drainage | 2024-07-05 |
| 6 | 45 | Drainage | 2024-07-06 |
| 7 | 112 | Water | 2024-06-29 |
| 8 | 112 | Water | 2024-06-30 |
| 9 | 112 | Water | 2024-07-01 |
| 10 | 112 | Water | 2024-07-02 |
| 11 | 7 | Garbage | 2024-07-01 |
| 12 | 7 | Garbage | 2024-07-03 |
Output
| ward_no | streak_start | streak_end | streak_days |
|---|---|---|---|
| 45 | 2024-07-01 | 2024-07-03 | 3 |
| 112 | 2024-06-29 | 2024-07-02 | 4 |
How to solve Wards With Complaint Streaks of Three Days or More
This is gaps and islands on dates. After SELECT DISTINCT ward_no, logged_on there is one row per active day. Number those days per ward with ROW_NUMBER(). On consecutive dates the day count since a fixed epoch (DATEDIFF(logged_on, '2000-01-01')) and the row number both rise by one, so their difference is the same for every day of a run; a missing day makes the date jump by two or more while the row number rises by one, and the difference changes. That difference is the island key: group by ward and key, keep groups of three or more, and the first and last dates are the streak's ends.
De-duplicating first is essential — ward 45 logged two complaints on 2 July, and without DISTINCT the extra row would shift the numbering and split the streak.
The first alternative marks a day that does not follow the previous one (LAG with a gap other than 1) and turns the marks into streak numbers with a running SUM. The second pairs each streak start (no complaint the day before) with the nearest streak end (no complaint the day after). The window versions are one sort per ward; the pairing version is quadratic but uses only joins.
Reference solution (MySQL)
WITH days AS (
SELECT DISTINCT ward_no, logged_on FROM complaint_log
),
islands AS (
SELECT ward_no, logged_on,
DATEDIFF(logged_on, '2000-01-01') - ROW_NUMBER() OVER (PARTITION BY ward_no ORDER BY logged_on) AS island
FROM days
)
SELECT ward_no, MIN(logged_on) AS streak_start, MAX(logged_on) AS streak_end, COUNT(*) AS streak_days
FROM islands
GROUP BY ward_no, island
HAVING COUNT(*) >= 3
ORDER BY ward_no, streak_startAnother way
WITH days AS (SELECT DISTINCT ward_no, logged_on FROM complaint_log),
flagged AS (
SELECT ward_no, logged_on,
CASE WHEN DATEDIFF(logged_on, LAG(logged_on) OVER (PARTITION BY ward_no ORDER BY logged_on)) = 1 THEN 0 ELSE 1 END AS starts_streak
FROM days
),
numbered AS (
SELECT ward_no, logged_on,
SUM(starts_streak) OVER (PARTITION BY ward_no ORDER BY logged_on ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS streak_no
FROM flagged
)
SELECT ward_no, MIN(logged_on) AS streak_start, MAX(logged_on) AS streak_end, COUNT(*) AS streak_days
FROM numbered GROUP BY ward_no, streak_no HAVING COUNT(*) >= 3
ORDER BY ward_no, streak_startAnother way
WITH days AS (SELECT DISTINCT ward_no, logged_on FROM complaint_log)
SELECT s.ward_no, s.logged_on AS streak_start, MIN(e.logged_on) AS streak_end, DATEDIFF(MIN(e.logged_on), s.logged_on) + 1 AS streak_days
FROM days s
JOIN days e ON e.ward_no = s.ward_no AND e.logged_on >= s.logged_on
WHERE NOT EXISTS (SELECT 1 FROM days p WHERE p.ward_no = s.ward_no AND p.logged_on = DATE_SUB(s.logged_on, INTERVAL 1 DAY))
AND NOT EXISTS (SELECT 1 FROM days n WHERE n.ward_no = e.ward_no AND n.logged_on = DATE_ADD(e.logged_on, INTERVAL 1 DAY))
GROUP BY s.ward_no, s.logged_on
HAVING DATEDIFF(MIN(e.logged_on), s.logged_on) + 1 >= 3
ORDER BY s.ward_no, streak_start← Change Between a Donor's First and Latest Gift · Reservation Holders to Notify After Today's Returns →