Buildings With an Ocean View

Buildings With an Ocean View

What is this problem about?

The Buildings With an Ocean View interview question asks you to identify which buildings in a row have an unobstructed view of the ocean. You are given an array heights where heights[i] is the height of the i-th building. The ocean is to the right of the last building. A building has an ocean view if all the buildings to its right are strictly shorter than it. The goal is to return a list of indices of buildings that have an ocean view, sorted in increasing order. This Buildings With an Ocean View coding problem is a classic example of "look-ahead" processing.

Why is this asked in interviews?

Tech companies like Meta and Google use this question to test a candidate's ability to efficiently process linear data. It evaluates whether you can avoid a naive O(N^2) solution (checking every building to the right for every building) in favor of a more optimal O(N) approach. It also tests your familiarity with monotonic stacks or simple backward iteration.

Algorithmic pattern used

This problem follows the Array, Monotonic Stack, Stack interview pattern. There are two main ways to solve it:

1. Backward Iteration: Traverse the array from right to left, keeping track of the max_height seen so far. If a building is taller than max_height, it has a view.
2. Monotonic Stack: Traverse from left to right. Maintain a stack of indices such that the heights are strictly decreasing. When you see a taller building, pop from the stack until the top building is taller or the stack is empty.

Example explanation

Suppose heights = [4, 2, 3, 1].

1. Building at index 3 (height 1) always has a view. max_height = 1.
2. Building at index 2 (height 3) is > 1. It has a view. max_height = 3.
3. Building at index 1 (height 2) is < 3. No view.
4. Building at index 0 (height 4) is > 3. It has a view. Indices with views: [0, 2, 3].

Common mistakes candidates make

• Inefficient nested loops: Checking every building to the right for every single building, which leads to time-limit exceeded (TLE) errors for large inputs.
• Strictly taller vs. equal: Forgetting that if a building to the right is the same height, it still blocks the view. The condition is strictly shorter.
• Sorting indices: Forgetting that if you iterate backward, the resulting list must be reversed to be in increasing order.

Interview preparation tip

Whenever a problem involves "elements to the right that are larger/smaller," think of Monotonic Stacks or Backward Iteration. These are the most common patterns for optimizing range-based comparisons in linear time.