Buildings With an Ocean View

medium monotonic stack array

Problem

Given building heights left-to-right with the ocean on the right, return indices of buildings whose view to the right is unobstructed (strictly taller than everything after).

Inputheights = [4,2,3,1]

Output[0,2,3]

Building at index 1 (height 2) is blocked by index 2 (height 3).

heights

def find_buildings(heights):
    out = []
    cur_max = 0
    for i in range(len(heights) - 1, -1, -1):
        if heights[i] > cur_max:
            out.append(i)
            cur_max = heights[i]
    out.reverse()
    return out

function findBuildings(heights) {
  const out = [];
  let m = 0;
  for (let i = heights.length - 1; i >= 0; i--) {
    if (heights[i] > m) { out.push(i); m = heights[i]; }
  }
  return out.reverse();
}

class Solution {
    public int[] findBuildings(int[] heights) {
        List<Integer> rev = new ArrayList<>();
        int m = 0;
        for (int i = heights.length - 1; i >= 0; i--) {
            if (heights[i] > m) { rev.add(i); m = heights[i]; }
        }
        Collections.reverse(rev);
        int[] out = new int[rev.size()];
        for (int i = 0; i < out.length; i++) out[i] = rev.get(i);
        return out;
    }
}

vector<int> findBuildings(vector<int>& heights) {
    vector<int> out;
    int m = 0;
    for (int i = (int)heights.size() - 1; i >= 0; i--) {
        if (heights[i] > m) { out.push_back(i); m = heights[i]; }
    }
    reverse(out.begin(), out.end());
    return out;
}

Explanation

A building can "see the ocean" only if every building to its right is shorter than it. The key insight is that the only thing standing between a building and the ocean is the tallest building to its right.

So we scan the array right-to-left and keep a running cur_max of the tallest height seen so far on the right side. A building has an ocean view exactly when its height is strictly greater than that running maximum.

Whenever a building beats cur_max, we record its index and update cur_max to its height. Since we collected indices from right to left, we reverse the result at the end so it reads left-to-right.

Example: heights = [4, 2, 3, 1]. From the right: 1 sees ocean (max becomes 1), 3 beats 1 so it sees ocean (max becomes 3), 2 is blocked by 3, 4 beats 3 so it sees ocean. Collected indices reversed give [0, 2, 3].

This works in a single pass with just one tracking variable, which is why it is both fast and uses constant extra space.

Time: O(n) Space: O(1)