Gaps and Islands в SQL: находим пробелы и серии подряд

1 задач Лёгкие, средние, сложные С эталонными решениями Решение в браузере
Gaps and islands — тот вопрос, на котором спотыкаются даже те, кто уверенно пишет оконки. Задача звучит безобидно: «Есть таблица активности юзера по дням — найди максимальную серию подряд идущих дней» или «Пользователь платил каждый месяц, покажи периоды непрерывной подписки». Пробелы (gaps) — это дыры в последовательности, острова (islands) — непрерывные куски. Главный трюк, который хотят от вас услышать: разность между значением и его порядковым номером ROW_NUMBER() постоянна внутри одной серии. Вычитаете row_number из даты — получаете якорь группы, по нему GROUP BY, и вот уже серии сгруппированы. На собесе в Ozon, Яндексе, Авито это любят давать как задачу на retention и активность: «сколько дней подряд юзер заходил», «периоды без заказов». Если сходу вспоминаете про группировку по разности — сигнал, что вы работали с временными рядами по-настоящему, а не только считали SUM по группам.
Начать решать задачи →

Все задачи на «gaps-and-islands» (1)

FAQ: частые вопросы про gaps-and-islands

В чём главная идея решения gaps-and-islands?

Для «островов» присваиваете строкам ROW_NUMBER() ORDER BY дате, а затем считаете разность между датой (или её порядковым номером) и этим row_number. Внутри непрерывной серии эта разность постоянна: например, для дат 1,2,3 с номерами 1,2,3 разность везде даёт одно значение, а на дате 5 она скакнёт. По этой разности делаете GROUP BY и получаете MIN(date), MAX(date), COUNT(*) для каждого острова. Для целочисленных дат работает date - row_number, для реальных дат — date - (row_number * interval '1 day') или сравнение через generate_series.

Как найти именно пробелы (gaps), а не серии?

Самый чистый способ — оконная функция LEAD: SELECT id + 1 AS gap_start, next_id - 1 AS gap_end FROM (SELECT id, LEAD(id) OVER (ORDER BY id) AS next_id FROM t) s WHERE next_id - id > 1. Здесь LEAD берёт следующее значение, и если разрыв больше 1, между текущим и следующим есть дыра. Для дат аналогично: LEAD(dt) OVER (ORDER BY dt), а условие next_dt > dt + interval '1 day'. Так вы возвращаете границы каждого пропуска, а не просто факт его наличия.

Как посчитать максимальную серию подряд идущих дней активности?

Сначала оставляете уникальные дни активности (DISTINCT date), затем внутри CTE считаете grp = date - (ROW_NUMBER() OVER (ORDER BY date) * interval '1 day')::int по каждому пользователю с PARTITION BY user_id. Дальше GROUP BY user_id, grp и берёте COUNT(*) AS streak_len, MIN(date), MAX(date). Финальным шагом MAX(streak_len) по пользователю или через ROW_NUMBER/RANK по убыванию длины выбираете топовую серию. Именно так на собесе просят решить «longest login streak».

Почему нельзя обойтись обычным GROUP BY без оконок?

Обычный GROUP BY группирует по значению колонки, а острова определяются не значением, а соседством строк — их непрерывностью. Без оконной функции у вас нет способа узнать «а какой день был предыдущим». Поэтому либо ROW_NUMBER/LAG/LEAD, либо рекурсивный CTE, который идёт по цепочке. На чистом агрегате задача не решается, и если кандидат пытается — это сразу видно интервьюеру.

Есть ли подвох с дублями и пропущенными датами?

Да, два классических подвоха. Первый: если в данных есть дубли дат (юзер заходил дважды в день), метод разности сломается — сначала обязательно DISTINCT или GROUP BY date. Второй: метод island через date - row_number корректен только для равномерного шага (день, месяц). Если шаг плавающий или нужны серии по «не более N дней разрыва», переходят к LAG + условной сумме: island_id = SUM(CASE WHEN dt - prev_dt > interval '1 day' THEN 1 ELSE 0 END) OVER (ORDER BY dt), что даёт нарастающий id новой серии при каждом разрыве.

Связанные темы SQL

Агрегации · JOIN-запросы · Оконные функции · CTE (Common Table Expressions) · Подзапросы · Работа с датами · Строковые функции · Условная логика

Открыть весь SQL-тренажёр (565 задач) →