Buildings with ocean view

Use a monotonic stack to find indices of buildings with an unobstructed ocean view.

stack monotonic-stack arrays

You are given a list of non-negative integers `heights` representing building heights from west to east. The ocean is to the east (right side). A building has an ocean view if it is strictly taller than every building to its east (i.e., for every j > i, heights[j] < heights[i]). The last building always has a view. Write a function `ocean_view(heights: List[int]) -> List[int]` that returns the indices of all buildings with an ocean view, sorted in ascending order. For example, `ocean_view([4,2,3,1])` returns `[0,2,3]` because building 0 (height 4) is taller than all to its right, building 2 (height 3) is taller than building 3, and building 3 (height 1) has no buildings to its right. The output must be sorted in ascending index order.

Constraints

The input `heights` is a list of non-negative integers. The length of `heights` is between 0 and 10^5. Each height is an integer between 0 and 10^9. The solution should run in O(n) time and O(n) space in the worst case.

Example

>>> ocean_view([4,2,3,1])
[0,2,3]
>>> ocean_view([1,3,2,4])
[3]
>>> ocean_view([])
[]

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Scan from right to left and track the maximum height seen so far.

A building has a view if its height is greater than the maximum height to its right.

Consider using a stack to maintain a decreasing sequence of heights as you traverse from right to left.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.