Buildings With an Ocean View

How it works

The most elegant approach is to scan from right to left. A building has an ocean view if it is strictly taller than every building to its right. We only need to track the maximum height seen so far as we traverse from the rightmost building toward the left.

Steps

1. Start from the rightmost building (it always has an ocean view) and add it to the result.
2. Move leftward through the buildings.
3. For each building, if its height is greater than the height of the last building added to our result (which represents the tallest building seen so far), add this building to the result.
4. Reverse the result since we collected indices from right to left but need them in increasing order.
5. Return the result.

Complexity

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

Things to watch for

Using Wrong Comparison Operator

A building loses its ocean view if any building to its right is taller OR EQUAL in height. Using strictly greater than (>) instead of greater than or equal (>=) incorrectly keeps buildings that are blocked by same-height buildings.

Forgetting to Reverse the Result

When iterating from right to left (the optimal approach), indices are collected in reverse order. Forgetting to reverse the final result returns indices in descending order instead of the required ascending order.

Not Handling Single Building Case

An array with one building should return [0] since the only building always has an ocean view. Edge case handling ensures the rightmost building is always included in the initial result.

from typing import List

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

class Solution {
public:
    vector<int> findBuildings(vector<int>& heights) {
        vector<int> res;
        int n = heights.size();
        res.push_back(n - 1);

        for (int i = n - 2; i >= 0; i--) {
            if (heights[i] > heights[res.back()]) {
                res.push_back(i);
            }
        }

        reverse(res.begin(), res.end());
        return res;
    }
};