Buildings With an Ocean View

Problem Statement

In this problem, we're presented with a scenario where there are n sequential buildings, each with a distinct height, along a line adjacent to an ocean. The ocean is positioned to the right end of this line of buildings. A building is defined to have an "ocean view" if there are no taller buildings to its right, allowing an unobstructed view of the ocean. Our task is to find out which buildings have such unobstructed views.

We will determine which buildings meet the criteria of an ocean view by examining their heights relative to the buildings to their right. The results are returned as a list of indices, in increasing order, representing the buildings that have an ocean view. The indices are 0-based, meaning that the first building in the sequence is indexed as 0, the second as 1, and so on up to n-1.

Examples

Example 1

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

Input:

heights = [4,3,2,1]

Output:

[0,1,2,3]

Explanation:

All the buildings have an ocean view.

Example 3

Input:

heights = [1,3,2,4]

Output:

[3]

Explanation:

Only building 3 has an ocean view.

Constraints

• 1 <= heights.length <= 105
• 1 <= heights[i] <= 109

Approach and Intuition

Understanding the problem and constructing an efficient approach can be broken down into the following steps:

1. Begin evaluating buildings from the rightmost side towards the left. This right-to-left approach allows us to keep track of the tallest building encountered so far and compare each building against this maximum.
2. Maintain a list where we'll append indices of the buildings which have a view of the ocean.
3. Initialize a variable, say max_height_so_far, to 0 or the minimum possible height, which will record the height of the tallest building observed as we iterate from right to left.
4. Iterate through the array of building heights in reverse. For each building, compare its height with max_height_so_far:
   • If the current building's height is greater than max_height_so_far, it means this building has an ocean view. Update max_height_so_far to this new height and add the building's index to our list of ocean-view buildings.
   • If not, simply continue to the next building.
5. Since the iteration is from right to left, and results need to be in increasing order of their indices, reverse the list of indices collected.
6. The final list will give the indices of all buildings that have an unobstructed view of the ocean, sorted from left to right.

This approach is efficient as it leverages a single scan of the list from right to left, and a simple comparison operation, making it optimal given the constraints of the problem.

Solutions

class Solution {
public:
    vector<int> findOceanViewBuildings(vector<int>& heights) {
        int totalBuildings = heights.size();
        vector<int> result;
        int tallestSoFar = -1;
            
        for (int index = totalBuildings - 1; index >= 0; --index) {
            if (tallestSoFar < heights[index]) {
                result.push_back(index);
                tallestSoFar = heights[index];
            }
        }
            
        reverse(result.begin(), result.end());
        return result;
    }
};