Same Reading Three Times in a Row
Problem
A sensor appends one row per reading to reading(id, value). The id column counts up by exactly 1 per row with no gaps, so it records the order the readings arrived in. Write a query that returns every value that was read at least three times in a row, as a single column value, sorted, with each value listed once.
Examples
Input: reading = [(1, 1), (2, 1), (3, 1), (4, 2), (5, 1), (6, 2), (7, 2)]
Output: [(1,)]
Why: rows 1 to 3 all read 1; 2 appears three times but never three rows in a rowInput: reading = [(1, 7), (2, 7), (3, 7), (4, 7), (5, 3), (6, 3), (7, 3)]
Output: [(3,), (7,)]
Why: a run of four 7s contains two runs of three, but 7 is still listed onceInput: reading = [(1, 5), (2, 5)]
Output: []
Why: edge case, two equal rows are not enoughHints
0 / 3
A row starts a run of three exactly when the row after it and the row after that hold the same value. The ids tell you which rows those are.
Join the table to itself twice: a second copy matched on id + 1 and a third copy matched on id + 2, each also required to have the same value as the first.
An INNER JOIN drops every row that has no matching partner, so what survives are the starting rows of runs. A run longer than three starts more than once, so finish with SELECT DISTINCT and ORDER BY.
Solution
Give the table three aliases and let the join conditions describe the shape of a run: b is the row right after a and c the row after that, and both must hold a's value. An inner join keeps only the combinations where all three rows exist and agree, so each surviving a row is the first reading of a run of at least three. A run of four starts twice (at its first and second row) and a value can have several separate runs, which is why the query needs DISTINCT. The join works because the ids have no gaps; if they could, you would number the rows yourself with ROW_NUMBER() or compare neighbours with LAG. With the primary key index each join lookup is O(log n), so the whole query runs in O(n log n).
import sqlite3
QUERY = """
SELECT DISTINCT a.value
FROM reading AS a
JOIN reading AS b ON b.id = a.id + 1 AND b.value = a.value
JOIN reading AS c ON c.id = a.id + 2 AND c.value = a.value
ORDER BY a.value
"""
def run(rows):
db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE reading (id INTEGER PRIMARY KEY, value INTEGER)")
db.executemany("INSERT INTO reading VALUES (?, ?)", rows)
return db.execute(QUERY).fetchall()
print(run([(1, 1), (2, 1), (3, 1), (4, 2), (5, 1), (6, 2), (7, 2)])) # -> [(1,)]
print(run([(1, 7), (2, 7), (3, 7), (4, 7), (5, 3), (6, 3), (7, 3)])) # -> [(3,), (7,)]
print(run([(1, 5), (2, 5)])) # -> []Stuck on the idea rather than the code? INNER and OUTER JOINs covers it.