The Algorithm
Explore the Sunset Hills solution with detailed code explanation
Algorithm Approach
The most efficient solution uses a left-to-right scan with a running maximum. The sunset is to the WEST (left side) of the array. As we iterate from left to right, we track the tallest building seen so far. A building can see the sunset if it's taller than all buildings to its left.
Complexity Analysis
O(n) Single pass through array
O(1) Constant extra space
Step-by-Step Process
- Start from the leftmost building (it always sees the sunset - nothing to its left)
- Track the maximum height encountered so far
- For each building moving right: if it's taller than the max, it can see the sunset
- Update the maximum height after each comparison
- Return the indices of buildings with sunset view
Implementation
Example Walkthrough
Input: [71, 55, 50, 65, 95, 68, 28, 34, 14]
| Index | Height | Max So Far | Can See Sunset? |
|---|---|---|---|
| 0 | 71 | 0 | Yes (71 > 0, leftmost) |
| 1 | 55 | 71 | No (55 ≤ 71) |
| 2 | 50 | 71 | No (50 ≤ 71) |
| 3 | 65 | 71 | No (65 ≤ 71) |
| 4 | 95 | 71 | Yes (95 > 71) |
| 5 | 68 | 95 | No (68 ≤ 95) |
| 6 | 28 | 95 | No (28 ≤ 95) |
| 7 | 34 | 95 | No (34 ≤ 95) |
| 8 | 14 | 95 | No (14 ≤ 95) |
Output: [0, 4]
(Buildings 1 and 5 can see the sunset to the WEST)
Related Problems
This algorithm is similar to:
- Trapping Rain Water
- Next Greater Element
- Stock Span Problem