Many people dream of living by the sea. And some of them actually move there. But being close to the beach does not always mean having a view. You can be only a few steps from the shore and still never see the water. The problem is not distance. The problem is height.

This is today’s setting: a row of buildings of different heights, with the ocean on one side. Before we solve anything, let’s pin down what “having a view” actually means.

What Does “Having a View” Mean?

Imagine the ocean is on the left. A building has an ocean view if every building between it and the ocean is strictly shorter. A single building ahead that is equal in height is enough to block the view entirely.

Let’s walk through a concrete example with heights [1, 3, 2, 4]:

The building at height 4 (the farthest from the ocean) looks toward the ocean and sees heights 1, 3, 2 in front of it. All of them are shorter. So it has a view. ✓
The building at height 2 sees heights 1 and 3. The building of height 3 is taller. View blocked. ✗
The building at height 3 sees only height 1 in front. That’s shorter. View clear. ✓
The building at height 1 is closest to the ocean. Nothing stands between it and the water. It always has a view. ✓

So for [1, 3, 2, 4], the buildings that have a view are at indices 0, 1, and 3.

Try editing the heights below and see which buildings end up with a view:

heights =(0-9)

Now that we know what it means for one building to have a view, the real question is: how do we find all buildings with a view efficiently?

The Naive Approach

A natural first step is to check each building individually. For every building, we scan all the buildings between it and the ocean and ask: “Is there anything taller?”

If we find even one building taller or equal, the view is blocked. If we reach the ocean without finding one, the building has a view.

This is straightforward to implement and easy to reason about. The issue is how much work it requires.

The Cost of Looking at Everything

Think about how many comparisons we make:

The first building (closest to the ocean) compares with nothing.
The second building compares with 1 building.
The third building compares with 2 buildings.
…and so on until the last one, which compares with n − 1 buildings.

If we draw a matrix where each column is a building and each row is a comparison it performs, we get a triangular pattern. Roughly half of an n × n grid.

heights =(0-9)

Loading…

The total number of comparisons grows as $\frac{n(n-1)}{2}$ , which is $\mathcal{O}(n^2)$ . For small inputs this is fine. For larger ones — say tens of thousands of buildings — this becomes slow.

The algorithm is correct, but it does not scale well.

Finding the Pattern

Before jumping to code, let’s try to understand why this can be done faster.

Consider the sequence [3, 1, 2]. The first building has height 3. It sees the ocean with nothing in its way. View clear. Now look at building 2 (height 1): there is a building of height 3 in front of it. Blocked. Building 3 (height 2): same, height 3 blocks it. So only the first building has a view.

Let’s extend it: [3, 1, 2, 3]. Can the new building at height 3 see the ocean? No. Even though it’s the same height as the first building, there is a building equally tall in front of it. Recall the rule: the view is blocked if any building ahead is equal or taller. So this building is also blocked.

Now add one more: [3, 1, 2, 3, 4]. The new building has height 4, which is taller than everything before it. Nothing ahead can block it. View clear.

Do you see the pattern?

A building has a view if and only if it is strictly taller than every building between it and the ocean. In other words, it must set a new record — it must be the tallest building seen so far, scanning from the ocean inward.

This means we don’t need to look back at all previous buildings every time. We just need to remember one number: the tallest height encountered so far. If the current building beats that number, it has a view and becomes the new record.

Explore this idea interactively. Try the sequences from above, and then try longer ones like [3, 1, 2, 3, 4, 5, 3, 6]:

heights =(0-9)

The One-Pass Solution

The insight above leads to a simple and elegant algorithm:

Start with max_so_far = -1 (a sentinel value lower than any valid height, so the first building always counts as a new record).
Scan the buildings from left to right (from ocean to the farthest building).
For each building, check if its height is strictly greater than max_so_far.
If it is: record its index in the result, and update max_so_far.
If it isn’t: skip it. It can never have a view.

def ocean_views(heights: list[int]) -> list[int]:
    result = []
    max_so_far = -1  # heights are assumed to be >= 0

    for i, h in enumerate(heights):
        if h > max_so_far:  # strictly taller than everything to the left
            result.append(i)
            max_so_far = h

    return result

That’s the whole solution. Each building is visited exactly once. There is no inner loop. No looking back.

Complexity

Time complexity: $\mathcal{O}(n)$ .
We iterate through the list once. Each building is examined in constant time (one comparison and at most one append). The total work grows linearly with the number of buildings.

Space complexity: $\mathcal{O}(n)$ .
In the worst case (a strictly increasing sequence), every building has a view, so the output list stores n indices. In the best case (a strictly decreasing sequence), only the first building has a view. If you exclude the output list and count only auxiliary memory, the algorithm uses $\mathcal{O}(1)$ extra space.

Compared to the naive $\mathcal{O}(n^2)$ approach, this is a significant improvement. The naive algorithm does $\frac{n(n-1)}{2}$ comparisons. The one-pass algorithm does exactly $n$ .

# References