learn deep. ship safe.Practice testsFollow ByteMunSubscribe

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?

Written by Published Tests checked by Deepak
SQL · standard syntax, runs on SQLite
Case 1
Table readings
idvalue
17
27
37
42
62
97
Expected (1 row)
7
Case 2
Table readings
idvalue
11
22
31
42
Expected (0 rows)

Run checks these 2 samples. Submit checks all 6 tests, including hidden ones.

  1. Top Three Salaries per DepartmentWindow functions · SQL
    hard
  2. Daily Sales Running TotalWindow functions · GROUP BY and aggregates · SQL
    medium
  3. Highest Paid Employee in Each DepartmentJoins · GROUP BY and aggregates · Window functions · SQL
    medium
  4. Find Duplicate EmailsGROUP BY and aggregates · SQL
    easy