# Buildings With an Ocean View

## 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]
```