Buildings With an Ocean View — LC Medium (easy)

Companies: Facebook

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:

Input: heights = [4,2,3,1]
Output: [0,2,3]
Explanation: Building 1 (0-indexed) does not have an ocean view because building 2 is taller.

Example 2:

Input: heights = [4,3,2,1]
Output: [0,1,2,3]
Explanation: All the buildings have an ocean view.

Example 3:

Input: heights = [1,3,2,4]
Output: [3]
Explanation: Only building 3 has an ocean view.

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 = [3]

# 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:

class Solution:
def findBuildings(self, heights: List[int]) -> List[int]:
heights = heights[::-1]
stack = []
curMax = float('-inf')
# now the heights will be [1,3,2,4]
for idx, height in enumerate(heights):
if height > curMax:
stack.append(len(heights) - idx - 1)
curMax = max(curMax, height)

return stack[::-1]

Time complexity: O(N)

space complexity: O(N) including answer list

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store