# Buildings With an Ocean View — LC Medium (easy)

1762. Buildings With an Ocean View

There are `n` buildings in a line. You are given an integer array `heights` of size `n` that represents the heights of the buildings in the line.

The ocean is to the right of the buildings. A building has an ocean view if the building can see the ocean without obstructions. Formally, a building has an ocean view if all the buildings to its right have a smaller height.

Return a list of indices (0-indexed) of buildings that have an ocean view, sorted in increasing order.

Example 1:

Example 2:

Example 3:

Constraints:

• `1 <= heights.length <= 105`
• `1 <= heights[i] <= 109`

My first approach:

when we have an ocean view at the rightmost side of the list, think reversely and assume that the ocean is at the leftmost side of the list. then, we will reverse the list, and iterate through all the heights and keep track of the current Maximum height as we go by.

example: [4,2,3,1] → [4, 3, 1] will have ocean views, in index, we have [0,2,3]

reversing the list, it becomes [1,3,2,4], and now the ocean is on the left.

assume that initial maximum is -inf. then as we iterate through, we are able to keep track of all the buildings (including first one) and identify which building is higher than the current maximum

# run 1: element #1: 1

1 is greater than -inf, so our current maximum becomes 1, and it is at the index position of 0. however when we append it to stack, we should take original index position minus the reversed index position to get the original index position.

height: 1

curMax: max( -inf, 1) => 1

index position: 4 (original length) — 0 (current index position) — 1 (0-indexed factor)

stack = 

# run 2: element #2: 3

height: 3

curMax: max(1,3) => 3

index Position: 4–1–1 = 2

stack = [3,2]

# run 3: element #3: 2

height: 2

curMax: max(3,2) => 3, # height is smaller than curMax, so we ignore this element

# run 4: element #4: 4

height: 4

curMax: max(3,4) => 4,

index Position: 4–3–1 = 0

stack: [3,2,0]

when we return it, we reverse the stack.

and = [0,2,3]

code:

Time complexity: O(N)

space complexity: O(N) including answer list

--

--

## More from Paul Kang

Data Scientist, SWE + MLE