DSA problem
Buildings With an Ocean View
There are n buildings in a line, with the ocean to the right (at index n). The i-th building has height heights[i]. A building has an ocean view if every building to its right is shorter than it — strictly shorter. Return a list of indices, in increasing order, of all buildings that have an ocean view.
The brute force checks each index i against every later index j and confirms that heights[j] < heights[i], costing O(n²) time. While simple, this is wasteful because once you know a building is taller than all buildings to its right, you have already accumulated the relevant max for free.
A cleaner approach scans right-to-left tracking the maximum height seen so far. For each index, if its height is strictly greater than the running max, it has an ocean view and we record the index; then we update the running max. Reverse the list of recorded indices at the end (since the problem requires increasing order). This solves the problem in O(n) time and O(1) extra space beyond the answer.
Equivalently, a monotonic decreasing stack of indices iterated left-to-right also works: any time you see a height that is >= the stack's top, pop the top (it can no longer have an ocean view). The indices remaining on the stack at the end are exactly the answer.
Examples
heights = [4,2,3,1][0,2,3]heights = [4,3,2,1][0,1,2,3]heights = [1,3,2,4][3]Constraints
- 1 <= heights.length <= 10^5
- 1 <= heights[i] <= 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.