Ближайшая банка нужного цвета

Средняя

На полке в ряд стоят банки с краской, paints[i] — цвет банки на позиции i. Цветов всего три: 1, 2 и 3. Каждый запрос queries[j] = [i, c] спрашивает: на каком наименьшем расстоянии от позиции i стоит банка цвета c? Расстояние между позициями a и b — это |a - b|; если на позиции i уже стоит цвет c, ответ 0. Если банок цвета c на полке нет, ответ -1. Верните список ответов на запросы в их порядке.

Пример 1

paints=[3, 1, 1, 2, 3, 1], queries=[[0, 2], [3, 3], [5, 1], [2, 3]] → [3, 1, 0, 2]

От 0 до ближайшего цвета 2 (позиция 3) — 3 шага. От 3 до цвета 3 — по 1 шагу в обе стороны (позиция 4). Позиция 5 сама цвета 1 — 0. От 2 ближайший цвет 3 — позиция 0 или 4, 2 шага.

Пример 2

paints=[2, 2, 1], queries=[[1, 3], [0, 1]] → [-1, 2]

Цвета 3 в ряду нет — ответ -1. Ближайший цвет 1 от позиции 0 — на позиции 2.

Ограничения

1 ≤ len(paints) ≤ 5·10⁴
paints[i] ∈ {1, 2, 3}
1 ≤ len(queries) ≤ 5·10⁴
queries[j] = [i, c], 0 ≤ i < len(paints), c ∈ {1, 2, 3}

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Array Binary Search Dynamic Programming

Вход

paints=[3, 1, 1, 2, 3, 1], queries=[[0, 2], [3, 3], [5, 1], [2, 3]]

Ожидается

[3, 1, 0, 2]

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 91 тест на сервере, включая скрытые.