Buildings With An Ocean View - Leetcode Solution

The Buildings With An Ocean View problem on Leetcode asks us to find all the buildings in an array representing the heights of buildings that can be seen from a certain point in the East. The problem can be solved using a simple algorithm that involves iterating over the array from right to left while keeping track of the maximum height seen so far.

Algorithm:

1. Initialize an empty list to store the indices of the buildings that can be seen from the East.
2. Initialize the maximum height seen so far to 0.
3. Iterate over the array from right to left:
   • If the current building height is greater than the maximum height seen so far, add its index to the list of visible buildings.
   • Update the maximum height seen so far with the current building height.
4. Return the list of visible buildings in reverse order.

Example:

Let's consider an array representing the heights of buildings from left to right in a certain city:

[3, 1, 4, 5, 2]

Traversing the array from right to left, we can keep track of the maximum height seen so far and add indices of the buildings that are visible.

For the last building with height 2, the maximum height seen so far is 5. Since 2 is less than 5, this building cannot be seen, so we move on to the next building.

For the fourth building with height 5, the maximum height seen so far is 5. Since 5 is equal to 5, this building can be seen, so we add its index (3) to the list of visible buildings.

For the third building with height 4, the maximum height seen so far is 5. Since 4 is less than 5, this building cannot be seen, so we move on to the next building.

For the second building with height 1, the maximum height seen so far is 5. Since 1 is less than 5, this building cannot be seen, so we move on to the next building.

For the first building with height 3, the maximum height seen so far is 5. Since 3 is less than 5, this building cannot be seen, so we move on to the next building.

The list of visible buildings is [3] which contains the index of the building with height 5.

Code:

Here is the Python implementation of the algorithm:

class Solution: def findBuildings(self, heights: List[int]) -> List[int]: n = len(heights) visible = [] max_height = 0

    for i in range(n-1, -1, -1):
        if heights[i] > max_height:
            visible.append(i)
            max_height = heights[i]
    
    return visible[::-1]

The time complexity of this algorithm is O(n) since we iterate over the array only once. The space complexity is also O(n) since we need to store the list of visible buildings.

1