Buildings With an Ocean View

From naive comparisons to an elegant one-pass solution, visualized step by step

Press → or Space to continue

Many people dream of living by the sea. But being close does not always mean having a view. This building is only a few steps from the beach. Yet it will never see the ocean. The problem is not distance. The problem is height.

Highlight building in index 2

Problem introduction with a visualization of buildings and ocean view.

heights =(0-9)

Loading…

\mathcal{O}(n^2)

Let's try a couple of small examples and see what we can learn. Take: 3, 1, 2. The first one is already the tallest. So none of the ones behind it can have a view.

3, 1, 2

The only way something behind can get a view is if it becomes a new record. So if we add a 3 nothing changes. In real life you might argue it has a view... but in our problem definition, it doesn't. It's still blocked by the first building.

3, 1, 2, 3

If we add a 4 at the end, because 4 beats the maximum so far, it has a view. So here is the idea: as we move away from the ocean, we keep track of the tallest height up to this point. If the current building beats that value, it has a view, and we update the maximum.

3, 1, 2, 3, 4

3, 1, 2, 3, 4, 5, 3, 6

heights =(0-9)