1762. Buildings With an Ocean View - Explanation

Problem Link

Description

You are given an array of integers heights of size n representing a row of buildings, where heights[i] is the height of the ith building.

There is an ocean located to the far right of the buildings. A building has an ocean view if every building to its right is strictly shorter than it.

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

Example 1:

Input: heights = [4,2,3,2,1]

Output: [0,2,3,4]

Example 2:

Input: heights = [1,3,2,4,2,5,1]

Output: [5,6]

Example 3:

Input: heights = [9,8,7,7,6,5,4,3]

Output: [0,1,3,4,5,6,7]

Constraints:

• 1 <= heights.length <= 100,000.
• 1 <= heights[i] <= 1,000,000,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

class Solution:
    def findBuildings(self, heights: List[int]) -> List[int]:
        n = len(heights)
        res = []

        for i in range(n):
            flag = True
            for j in range(i + 1, n):
                if heights[i] <= heights[j]:
                    flag = False
                    break
            if flag:
                res.append(i)

        return res

Time & Space Complexity

• Time complexity: $O(n ^ 2)$
• Space complexity: $O(n)$ for the output array.

---

2. Monotonic Stack

class Solution:
    def findBuildings(self, heights: List[int]) -> List[int]:
        stack = []

        for i, h in enumerate(heights):
            while stack and heights[stack[-1]] <= h:
                stack.pop()
            stack.append(i)

        return stack

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

3. Greedy

class Solution:
    def findBuildings(self, heights: List[int]) -> List[int]:
        res = [len(heights) - 1]
        for i in range(len(heights) - 2, -1, -1):
            if heights[i] > heights[res[-1]]:
                res.append(i)
        res.reverse()
        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity:
  • $O(1)$ extra space.
  • $O(n)$ for the output array.