Overview

For buildings lined up in order from the sea side (front), this problem asks you to count the number of buildings visible from the sea (buildings taller than the previous maximum) while updating the “maximum height seen so far.”

Analysis

The condition for building \(i\) to be visible from the sea is: “if \(M\) is the maximum height among buildings \(1 \sim i-1\) in front of it, then \(H_i > M\).”
This means “only buildings that set a new record for maximum height are visible.”

Key Observation

• For a building not to be completely hidden by buildings in front, it must be taller than all buildings in front of it at some point.
• Therefore, by keeping track of the “maximum height so far,” we can determine whether each building is visible in a single check.

Why the Naive Approach Is Too Slow

If for each \(i\) we recompute the maximum of \(H_1 \sim H_{i-1}\) every time: - Finding the maximum for each building takes \(O(i)\) - The total becomes \(O(1+2+\cdots+N)=O(N^2)\)
which is too slow for \(N \le 2 \times 10^5\).

Solution

We scan from left to right, maintaining a variable max_h that stores the “maximum height seen so far.” - If \(H_i > max_h\), the building is visible → increment the count and update max_h - Otherwise, it is not visible

For example, when \(H=[3,2,5,5,4,6]\): - 3 (new maximum) → visible - 2 (at most 3) → not visible - 5 (new maximum) → visible - 5 (at most 5, equal) → not visible (the condition is \(>\)) - 4 (at most 5) → not visible - 6 (new maximum) → visible
So 3 buildings are visible.

Algorithm

1. Initialize max_h = -1, cnt = 0
2. Iterate through buildings from \(1\) to \(N\) in order
3. For height \(x=H_i\):
   • If \(x > max_h\), do cnt += 1 and update max_h = x
4. Output cnt at the end

This is the process of updating the “prefix maximum (maximum from the beginning)” as we scan from the front.

Complexity

• Time complexity: \(O(N)\) (each building is examined exactly once)
• Space complexity: \(O(1)\) (only the maximum and the count are stored; excluding the input array)

Implementation Notes

• The condition is \(H_i > M\), not \(H_i \ge M\) (buildings of equal height are treated as completely hidden).

• Since the input can be large, using sys.stdin.buffer.read() in Python allows for faster reading.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    n = int(data[0])
    h = list(map(int, data[1:1+n]))

    max_h = -1
    cnt = 0
    for x in h:
        if x > max_h:
            cnt += 1
            max_h = x
    print(cnt)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.