Overview

This problem asks us to count the number of buildings that are not completely hidden by buildings in front of them when viewed from the sea. This can be solved by counting “how many buildings exceed the maximum height seen so far.”

Analysis

Key Insight

Whether building \(i\) is visible from the sea depends on comparing its height \(H_i\) with the maximum height \(M\) of all buildings in front of it, and checking whether \(H_i > M\).

Let’s consider a concrete example. If the building heights are \([3, 1, 4, 1, 5]\):

Building #	Height	Max height in front	Visible?
1	3	0 (no buildings in front)	○
2	1	3	× (1 ≤ 3)
3	4	3	○ (4 > 3)
4	1	4	× (1 ≤ 4)
5	5	4	○ (5 > 4)

The answer is 3 (buildings 1, 3, 5).

Problem with the Naive Approach

If we calculate the maximum value from building \(1\) to \(i-1\) for each building \(i\), the time complexity becomes \(O(N^2)\). When \(N \leq 2 \times 10^5\), this is too slow.

Solution

Instead of recalculating the maximum each time, we can maintain the current maximum in a variable and update it as we go, allowing us to determine each building’s visibility in \(O(1)\).

Algorithm

1. Initialize max_height = 0 (maximum height so far) and count = 0 (number of visible buildings)
2. Process buildings from the sea side in order (\(i = 1, 2, \ldots, N\))
3. For each building:
   • If \(H_i > \text{max\_height}\), the building is visible, so increment count by 1
   • Update max_height to \(\max(\text{max\_height}, H_i)\)
4. Output the final count

This algorithm “counts the number of times we exceed the maximum value while updating the maximum of all values seen so far.”

Complexity

• Time complexity: \(O(N)\)
  • Because we only need to look at each building once
• Space complexity: \(O(N)\)
  • To store the input array \(H\)
  • (Can be reduced to \(O(1)\) if input is processed sequentially)

Implementation Notes

• By initializing max_height to \(0\), building 1 will always satisfy \(H_1 > 0\), automatically being judged as “visible” (since the problem constraint guarantees \(H_i \geq 1\))

• We update max_height inside the conditional because only visible buildings become new “blockers.” In practice, updating with non-visible buildings would give the same result, but updating only with visible buildings is more intuitive

  Source Code

N = int(input())
H = list(map(int, input().split()))

count = 0
max_height = 0

for h in H:
    if h > max_height:
        count += 1
        max_height = h

print(count)

---

This editorial was generated by claude4.5opus.