Buildings With an Ocean View

Medium

Asked by:

204 views

Topics:

Arrays

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 is strictly taller than all the buildings to its right.

Return a list of the indices of buildings that have an ocean view, sorted in ascending order.

Example 1:

Input: heights = [4,2,3,1]
Output: [0,2,3]
Explanation: Building at index 0 has a height of 4 and is taller than all the other buildings, so it has an ocean view.
Building at index 2 has a height of 3 and is taller than all the buildings to its right, so it has an ocean view.
Building at index 3 has a height of 1 and is taller than all the buildings to its right, so it has an ocean view.

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 the building at index 3 has an ocean view.

Constraints:

1 <= heights.length <= 10⁵
1 <= heights[i] <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the `heights` array?
Can the `heights` array contain negative values or zero?
If no buildings have an ocean view, what should the function return?
Are duplicate heights allowed in the `heights` array, and if so, how does that affect the determination of an ocean view?
Is there a specific data type required for the returned list of indices (e.g., ArrayList, LinkedList, plain array)?

Brute Force Solution

Approach

The brute force approach to finding buildings with an ocean view is to check each building individually. We'll assume a building has an ocean view unless we find evidence otherwise by checking all buildings to its right.

Here's how the algorithm would work step-by-step:

Start with the first building in the row.
Compare its height to the height of every building to its right.
If every building to its right is shorter or the same height, then the first building has an ocean view.
If any building to its right is taller, then the first building does not have an ocean view.
Move to the next building in the row and repeat the process of comparing it to all buildings to its right.
Continue this process for every building in the row.
After checking all buildings, list the buildings that have an unobstructed view of the ocean.

Code Implementation

def buildings_with_ocean_view_brute_force(building_heights):
    buildings_with_view = []
    number_of_buildings = len(building_heights)

    for current_building_index in range(number_of_buildings):
        has_ocean_view = True

        # Check all buildings to the right
        for comparison_building_index in range(current_building_index + 1, number_of_buildings):

            # Check if a taller building is blocking view
            if building_heights[comparison_building_index] >= building_heights[current_building_index]:
                has_ocean_view = False
                break

        # If no taller building was found, add to result
        if has_ocean_view:
            buildings_with_view.append(current_building_index)

    return buildings_with_view

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n buildings in the input array. For each building, it compares its height to the height of every building to its right. In the worst case, for each of the n buildings, it might need to compare with nearly n other buildings. This results in approximately n * n comparisons, and therefore the time complexity is O(n²).

Space Complexity

O(N) – The algorithm iterates through each building, and for each building, it potentially adds it to a list of buildings with an ocean view. In the worst-case scenario, all N buildings have an ocean view, resulting in a list of size N being stored. Therefore, the auxiliary space required to store the buildings with an ocean view scales linearly with the input size N. The final result is a list of at most size N, hence O(N) space complexity.

Optimal Solution

Approach

The goal is to find buildings with an unobstructed ocean view, meaning no taller building blocks its view to the right. The trick is to check buildings from right to left, keeping track of the tallest building we've seen so far. This way, we only need to look at each building once.

Here's how the algorithm would work step-by-step:

Start by looking at the building farthest to the right (the last building).
Assume this building has an ocean view, as there are no buildings to its right.
Remember the height of this building; this is the tallest building we've seen so far.
Move one building to the left.
If the current building is taller than the tallest building we've seen so far, it also has an ocean view.
If the current building has an ocean view, update the height of the tallest building we've seen so far to the height of the current building.
If the current building is shorter than or the same height as the tallest building we've seen so far, it does not have an ocean view.
Repeat steps 4 through 7 until you've checked all buildings.
The buildings you marked as having an ocean view are the answer.

Code Implementation

def find_buildings_with_ocean_view(building_heights):
    ocean_view_buildings = []
    tallest_building_so_far = 0

    # Iterate backwards as rightmost always has view
    for index in range(len(building_heights) - 1, -1, -1):
        current_building_height = building_heights[index]

        # Check if current building has ocean view
        if current_building_height > tallest_building_so_far:
            ocean_view_buildings.append(index)

            # Update the tallest building so far.
            tallest_building_so_far = current_building_height

    ocean_view_buildings.reverse()
    return ocean_view_buildings

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through the buildings array once, from right to left. In each iteration, it performs a constant amount of work: comparing the current building's height to the tallest building seen so far and potentially updating the tallest building. Therefore, the time complexity is directly proportional to the number of buildings, n, resulting in O(n).

Space Complexity

O(N) – The algorithm uses an output list (or equivalent data structure implicitly) to store the indices of the buildings with an ocean view. In the worst-case scenario, all buildings might have an ocean view, resulting in a list of size N, where N is the number of buildings. Additionally, it uses a constant amount of space for variables like the tallest building seen so far. Therefore, the dominant factor is the potential output list of size N, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty input array	Return an empty list as there are no buildings to consider.
Input array with only one building	Return a list containing only the index 0, as a single building always has an ocean view.
Buildings with monotonically increasing heights	Every building has an ocean view, so return a list of indices from 0 to n-1.
Buildings with monotonically decreasing heights	Only the last building has an ocean view, so return a list containing only the last index.
All buildings have the same height	Only the last building has an ocean view, so return a list containing only the last index.
Very large input array (performance considerations)	Iterate from right to left, keeping track of the maximum height seen so far, to achieve O(n) time complexity.
Input array contains zero height buildings	Zero height buildings are valid and should be processed like any other height.
Input array contains large integer heights (potential overflow)	Use integer comparison and avoid arithmetic operations that could lead to overflow, which can be achieved by comparing heights directly.

Empty input array

How to Handle:

Return an empty list as there are no buildings to consider.

Input array with only one building

How to Handle:

Return a list containing only the index 0, as a single building always has an ocean view.

Buildings with monotonically increasing heights

How to Handle:

Every building has an ocean view, so return a list of indices from 0 to n-1.

Buildings with monotonically decreasing heights

How to Handle:

Only the last building has an ocean view, so return a list containing only the last index.

All buildings have the same height

How to Handle:

Only the last building has an ocean view, so return a list containing only the last index.

Very large input array (performance considerations)

How to Handle:

Iterate from right to left, keeping track of the maximum height seen so far, to achieve O(n) time complexity.

Input array contains zero height buildings

How to Handle:

Zero height buildings are valid and should be processed like any other height.

Input array contains large integer heights (potential overflow)

How to Handle:

Use integer comparison and avoid arithmetic operations that could lead to overflow, which can be achieved by comparing heights directly.