Buildings With an Ocean View
Medium · Stack & Strings · Array · Stack · Monotonic Stack
Problem
There are n buildings in a row, and heights[i] is the height of building i. The ocean lies to the right of the last building.
A building has an ocean view if every building to its right is strictly shorter than it. Return the indices (0-indexed) of all buildings with an ocean view, in increasing order.
Examples
Input: heights = [4,2,3,1] Output: [0,2,3]
Building 1 (height 2) is blocked by building 2 (height 3). Buildings 0, 2 and 3 are taller than everything to their right.
Input: heights = [4,3,2,1] Output: [0,1,2,3]
Heights fall toward the ocean, so every building looks over the ones in front of it.
Input: heights = [2,2,2] Output: [2]
Only the last building sees the ocean: a building of equal height also blocks the view.
Constraints
- 1 <= len(heights) <= 10^5
- 1 <= heights[i] <= 10^9
Approaches
- Check every building to the right — time O(n²), space O(1) besides the answer
Follow-up
If buildings keep being added on the left of the street, the right-to-left scan simply continues: keep the running maximum and test each new building. If they are added on the right, by the ocean, the stack version fits: each new building pops the ones it blocks.
Related problems
Start free on Cariara · Coding problems · System design studio
