MediumArrayStackMonotonic StackUpdated Sep 2026

1762. Buildings With an Ocean View

Asked at Anduril

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Array

Companies

1

Problem

You are given an array heights. Each value is the height of a building, and the buildings stand in a straight line. The ocean is on the right side of the line.

A building can see the ocean only if nothing blocks it. That means every building to its right must be strictly shorter than it. If any building to the right is the same height or taller, the view is blocked.

Return the indices (0-based) of all buildings that can see the ocean, sorted in increasing order.

Who can see the ocean?

heights42310123Green buildings see the ocean; the red building atindex 1 is blocked by the taller building 3 at index2.
The ocean is on the right. A building sees it only if every building to its right is shorter.

Constraints

  • ●1 <= heights.length <= 10^5
  • ●1 <= heights[i] <= 10^9

Examples

Example 1
Inputheights = [4,2,3,1]
Output[0,2,3]
WhyBuilding 3 (height 1) is rightmost, so it sees the ocean. Building 2 (height 3) is taller than building 3, so it also sees the ocean. Building 1 (height 2) is blocked because building 2 (height 3) is taller. Building 0 (height 4) is taller than everything to its right, so it sees the ocean.
Example 2
Inputheights = [4,3,2,1]
Output[0,1,2,3]
WhyThe heights strictly decrease from left to right. Every building is taller than all buildings to its right, so all of them have a clear view.
Example 3
Inputheights = [1,3,2,4]
Output[3]
WhyBuilding 3 (height 4) is the tallest and is rightmost, so it sees the ocean. Buildings 0, 1 and 2 are all blocked by building 3, which is taller than each of them.

Asked At

1 companies
CompanyDifficulty
AndurilMediumView all Anduril questions →

How to Think About It

1

Checking every building against everything to its right is O(n²).

2

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.

3

Collect qualifying indices during the scan, then reverse them to get increasing order.

4

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.

5

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.

Scan from the ocean side

heights42310123iStart at the last building (height 1). tallest = 0, so1 > 0: it sees the ocean. Now tallest = 1.heights42310123iMove to index 2 (height 3). 3 > 1, so it sees theocean. Now tallest = 3.heights42310123iIndex 1 has height 2, which is not greater thantallest = 3, so it is blocked. tallest stays 3.heights42310123iIndex 0 has height 4 > 3, so it sees the ocean.Collected indices [3,2,0] reversed give [0,2,3].
Walk right to left and remember the tallest height seen so far. A building sees the ocean only if it beats that record.
ComplexityTime O(n)Space O(1)One right-to-left pass touches each building once; only a running maximum and the output list are kept.

What Trips People Up in Real Interviews

1

Using >=. A building of equal height to its right blocks the view — the comparison must be strict.

2

Forgetting to reverse the collected indices.

3

Scanning left to right with a running maximum. That checks the wrong side.

4

Not offering the stack version if the interviewer says heights arrive as a stream from the left.

Solution Code

O(n) time
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]

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

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 runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.