hardWindow functionsSQL
Value Repeated Three Times in a Row
Find values that appear in at least three consecutive rows of a log ordered by id, using LAG() or a self-join: a gaps-and-islands style SQL interview question.
SQL
The table readings(id, value) is a log of sensor readings. id is a unique, increasing integer that orders the log, but ids can have gaps (deleted rows), so consecutive means next to each other when ordered by id, not ids that differ by one.
Write a query that returns each value that appears in at least three consecutive rows. Return one column, value, each value once, in any order.
Examples
Example 1
Input: readings (id, value): (1, 7), (2, 7), (3, 7), (4, 2), (6, 2), (9, 7) Output: value 7 Why: 7 appears in rows 1, 2 and 3 in a row. 2 appears only twice in a row (ids 4 and 6 are neighbours because id 5 is missing).
Constraints
- ids are unique but may have gaps.
- A value that has three in a row anywhere counts, even if it also appears elsewhere.
- Return each qualifying value once.
Hints
Hint 1
LAG(value, 1) and LAG(value, 2) OVER (ORDER BY id) put the previous two readings on the current row.
Hint 2
A row ends a run of three when its value equals both previous values.
Hint 3
Self-joining on id + 1 breaks when ids have gaps: number the rows with ROW_NUMBER() first if you go that way.
Solution
Show the solution (try it yourself first)
Approach: look back two rows with LAG
LAG(value, n) OVER (ORDER BY id) returns the value n rows earlier in id order, regardless of gaps in the ids. A row whose value equals both of the two previous values is the third (or later) reading of a run, so its value qualifies. DISTINCT collapses repeated runs to one row.
WITH w AS (
SELECT value,
LAG(value, 1) OVER (ORDER BY id) AS prev1,
LAG(value, 2) OVER (ORDER BY id) AS prev2
FROM readings
)
SELECT DISTINCT value
FROM w
WHERE value = prev1 AND value = prev2;A common wrong answer self-joins r2.id = r1.id + 1: with a deleted row the neighbours no longer differ by one, so runs are missed or invented. If you prefer joins, number the rows with ROW_NUMBER() OVER (ORDER BY id) first and join on that number. The general pattern, grouping runs by ROW_NUMBER() - ROW_NUMBER() OVER (PARTITION BY value ...), is called gaps and islands.
Complexity
O(n log n) for the ordering (O(n) when MySQL reads the primary key in order), then one pass.
Found a mistake in this problem, its tests or the solution?