Problem

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.

Examples

Example 1:

1
2
3

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:

1
2
3

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

Example 3:

1
2
3

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

Constraints:

  • 1 <= heights.length <= 10^5
  • 1 <= heights[i] <= 109

Solution

Method 1 – Stack from Right

Intuition

A building has an ocean view if all buildings to its right are shorter. Traverse from right to left, keeping track of the maximum height seen so far.

Approach

  1. Start from the rightmost building, which always has an ocean view.
  2. For each building from right to left, if its height is greater than the max seen so far, add its index to the result.
  3. Reverse the result to get indices in increasing order.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import java.util.*;
class Solution {
    public int[] findBuildings(int[] heights) {
        int n = heights.length;
        List<Integer> res = new ArrayList<>();
        int maxH = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (res.isEmpty() || heights[i] > maxH) {
                res.add(i);
                maxH = heights[i];
            }
        }
        Collections.reverse(res);
        return res.stream().mapToInt(Integer::intValue).toArray();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def findBuildings(self, heights: list[int]) -> list[int]:
        n = len(heights)
        res = []
        max_h = 0
        for i in range(n-1, -1, -1):
            if not res or heights[i] > max_h:
                res.append(i)
                max_h = heights[i]
        return res[::-1]

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)