Code Implementation

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

class Solution {
public:
    vector<int> findBuildings(vector<int>& heights) {
        int n = heights.size();
        vector<int> res;
        int maxHeight = 0;
        for (int i = n - 1; i >= 0; --i) {
            if (heights[i] > maxHeight) {
                res.push_back(i);
                maxHeight = heights[i];
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};
      

class Solution {
    public int[] findBuildings(int[] heights) {
        List<Integer> res = new ArrayList<>();
        int maxHeight = 0;
        for (int i = heights.length - 1; i >= 0; --i) {
            if (heights[i] > maxHeight) {
                res.add(i);
                maxHeight = heights[i];
            }
        }
        Collections.reverse(res);
        return res.stream().mapToInt(i -> i).toArray();
    }
}
      

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

Problem Description

You are given an array heights where heights[i] represents the height of the i-th building in a row, with the ocean to the right of the last building. A building has an ocean view if all the buildings to its right are shorter. Return a list of indices of all buildings that have an ocean view, ordered from left to right.

• Each building can be used only once in the result.
• The returned indices must be in increasing order.

Thought Process

Let's start by understanding what it means for a building to have an ocean view: for building i, every building to its right (with index greater than i) must be shorter. A brute-force approach would be to, for each building, check all buildings to its right and see if any are taller or equal in height. However, this would be inefficient for large arrays.

If we think about the problem from the end (the ocean) moving left, we can keep track of the maximum height we've seen so far. If the current building is taller than any building to its right (i.e., taller than the current maximum), it has an ocean view. This observation allows us to solve the problem efficiently in a single pass.

Solution Approach

• Start from the last building (nearest the ocean) and move leftwards.
• Maintain a variable, say max_height, to keep track of the tallest building seen so far to the right.
• For each building, compare its height to max_height:
• If the current building is taller than max_height, it has an ocean view—add its index to the result.
• Update max_height if the current building is taller.
• Since we're traversing from right to left, the indices will be in reverse order. Reverse the result at the end to match the required left-to-right order.

This approach is efficient and only requires a single pass through the array, plus a reversal at the end.

Example Walkthrough

Let's use heights = [4, 2, 3, 1] as an example.

1. Start from the rightmost building (index 3, height 1). max_height = 0. 1 > 0, so index 3 is added. max_height = 1.
2. Move to index 2 (height 3). 3 > 1, so index 2 is added. max_height = 3.
3. Move to index 1 (height 2). 2 < 3, so it's skipped.
4. Move to index 0 (height 4). 4 > 3, so index 0 is added. max_height = 4.
5. The result list is [3, 2, 0] (right to left). Reverse it to [0, 2, 3].

Buildings at indices 0, 2, and 3 have an ocean view.

Time and Space Complexity

• Brute-force approach: For each building, check all buildings to its right. This is O(n²) time complexity, where n is the number of buildings.
• Optimized approach: We only make one pass from right to left (O(n)), and reverse the result (O(n)), so total time complexity is O(n).
• Space complexity is O(k) where k is the number of buildings with an ocean view (at most n), and O(n) is used for the result array.

Summary

The key insight is to process buildings from right to left, maintaining the maximum height seen so far. This allows us to efficiently determine which buildings have an ocean view in a single pass. The solution is both simple and effective, avoiding unnecessary comparisons and leveraging the problem's structure for a clean O(n) solution.