Ліхтар світить збоку першої будівлі, промені паралельні землі. Будівля освітлена, якщо хоч частина її стіни не затулена — а затуляють її лише будівлі, що стоять перед нею.
Отже, будівля освітлена тоді й лише тоді, коли її висота строго більша за висоти всіх попередніх:
Якщо знайдеться попередня будівля такої ж або більшої висоти, вона повністю перекриє промені, і жодного вільного метра стіни не залишиться.
Звідси розв'язок в один прохід: тримаємо поточний максимум висоти (спочатку ), для кожної будівлі порівнюємо її висоту з максимумом і, якщо вона більша, збільшуємо відповідь та оновлюємо максимум.
Перша будівля освітлена завжди, бо перед нею нічого немає, — початкове значення максимуму забезпечує це автоматично, адже H_i \ge 1.
Складність — , зберігати весь масив навіть не обов'язково.