Buildings With an Ocean View

Problem Id: 1762 Difficulty: Medium Tag: Greedy


Intuition

Knowing the Problem
  • The input of this problem is a simple array, where each number in this array represents the height of a building. The Ocean is in the right of all buildings.
  • The limitation introduced in this problem is that if a building is lower or equal to another building, it will be hiden and has no ocean view.
  • The output of this problem should be for each building, whether it can have ocean view. And the output should be an array where the ith element represents building res[i] has ocean view.
Idea

The basic idea of this problem is that, a building would have ocean view if and only if all it's right buildings are lower than it. So the problem becomes for each building, find the maximum building on it's right and compare this highest height with it's height.

For each building, if we want to get the highest building on it's right, we need to go through all buildings on it's right. However, if we calculate the highest value from right to left, then for each building, to calculate the highest building to right including it, we would only need to use the existing right maximum value and it's value.

Time Complexity

The overall time complexity is O(n) since we only need to go through the array once (from right to left).

About Code

The code is simple. We use a list ocean_views to store the indices with ocean view . And the prev_max_height is used to store the height of previous highest building.

Note: Don't forget to reverse before since we are handling from right to left.

Solution


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