Human Traffic of Stadium

hard database sql

Problem

Stadium(id, visit_date, people). Return rows with people ≥ 100 that participate in three consecutive ids.

Inputs=[(1,'D1',10),(2,'D2',109),(3,'D3',150),(4,'D4',99),(5,'D5',145),(6,'D6',1455),(7,'D7',199),(8,'D8',188)]
Output[(5,...),(6,...),(7,...),(8,...)]
Ids 5-8 form two overlapping triples of busy days.

SELECT DISTINCT s1.*
FROM Stadium s1, Stadium s2, Stadium s3
WHERE s1.people >= 100 AND s2.people >= 100 AND s3.people >= 100
  AND (
    (s1.id - s2.id = 1 AND s2.id - s3.id = 1) OR
    (s2.id - s1.id = 1 AND s1.id - s3.id = 1) OR
    (s3.id - s2.id = 1 AND s2.id - s1.id = 1)
  )
ORDER BY s1.id;
Time: O(n³) (three-copy self-join; O(n) if rewritten with LAG/LEAD window functions) Space: O(n)