Buildings With an Ocean View
Asked at Anduril
Problem
Buildings With an Ocean View gives you building heights in a line with the ocean to the right, and asks for the indices of buildings that can see the ocean — those strictly taller than every building to their right — in increasing order. A single right-to-left scan with a running maximum solves it.
Asked At
| Company | Difficulty | |
|---|---|---|
| Anduril | Medium | View all Anduril questions → |
How to Think About It
Checking every building against everything to its right is O(n²).
Key insight: scan from the ocean side (right to left) and track the tallest building seen so far. A building has a view iff it is strictly taller than that maximum.
Collect qualifying indices during the scan, then reverse them to get increasing order.
Left-to-right alternative: keep a monotonic stack; pop every building that is not taller than the current one (it just lost its view). The stack ends up holding exactly the answer in order.
Walkthrough for [4,2,3,1]: from the right, 1 (view, max 1), 3 (view, max 3), 2 (blocked), 4 (view). Reverse [3,2,0] -> [0,2,3].
Optimal Approach
Step 1: res = [], tallest = 0.
Step 2: For i from n-1 down to 0: if heights[i] > tallest, append i and set tallest = heights[i].
Step 3: Return res reversed.
Time: O(n). Space: O(1) besides the output.
What Trips People Up in Real Interviews
Using >=. A building of equal height to its right blocks the view — the comparison must be strict.
Forgetting to reverse the collected indices.
Scanning left to right with a running maximum. That checks the wrong side.
Not offering the stack version if the interviewer says heights arrive as a stream from the left.
Solution Code
def findBuildings(heights):
res = []
tallest = 0
for i in range(len(heights) - 1, -1, -1):
if heights[i] > tallest:
res.append(i)
tallest = heights[i]
return res[::-1]Frequently Asked Questions
What is the Buildings With an Ocean View problem?
Buildings With an Ocean View gives you building heights in a line with the ocean to the right, and asks for the indices of buildings that can see the ocean — those strictly taller than every building to their right — in increasing order. A single right-to-left scan with a running maximum solves it.
How do you solve Buildings With an Ocean View?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Buildings With an Ocean View?
Buildings With an Ocean View is asked at Anduril. It is a medium difficulty problem.
What are common mistakes on Buildings With an Ocean View?
- Using `>=`. A building of equal height to its right blocks the view — the comparison must be strict.
- Forgetting to reverse the collected indices.
- Scanning left to right with a running maximum. That checks the wrong side.
- Not offering the stack version if the interviewer says heights arrive as a stream from the left.