[Medium] 1762. Buildings With an Ocean View

There are n buildings in a line. You are given an integer array heights of size n that represents the heights of the buildings in the line.

The ocean is to the right of the buildings. A building has an ocean view if the building can see the ocean without obstructions. Formally, a building has an ocean view if all the buildings to its right have a smaller height.

Return a list of indices (0-indexed) of buildings that have an ocean view, sorted in increasing order.

Examples

Example 1:

Input: heights = [4,2,3,1]
Output: [0,2,3]
Explanation: Building at index 1 (height 2) does not have an ocean view because building at index 2 (height 3) is taller.

Example 2:

Input: heights = [4,3,2,1]
Output: [0,1,2,3]
Explanation: All the buildings have an ocean view.

Example 3:

Input: heights = [1,3,2,4]
Output: [3]
Explanation: Only building at index 3 (height 4) has an ocean view.

Example 4:

Input: heights = [2,2,2,2]
Output: [3]
Explanation: Only the rightmost building has an ocean view (buildings of equal height block the view).

Constraints

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

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

Ocean view definition: What gives a building an ocean view? (Assumption: Building has ocean view if no taller building to its right blocks the view)
Building positions: How are buildings positioned? (Assumption: Buildings are in a row, ocean is to the right - heights[i] is height of building at index i)
Return format: What should we return? (Assumption: Array of indices of buildings with ocean view, sorted in ascending order)
Height comparison: How do we check for blocking? (Assumption: Building at index i has ocean view if all buildings at indices > i have height <= heights[i])
Rightmost building: Does the rightmost building always have ocean view? (Assumption: Yes - no buildings to its right to block it)

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

For each building, check all buildings to its right to see if any building is taller or equal. If no taller building exists to the right, the building has an ocean view. This approach has O(n²) time complexity, which is inefficient for large arrays.

Step 2: Semi-Optimized Approach (7 minutes)

Traverse from right to left, maintaining the maximum height seen so far. For each building, if its height is greater than the maximum seen, it has an ocean view. Update the maximum. This achieves O(n) time with O(1) extra space. However, we need to collect indices in increasing order, which may require storing them and sorting, or processing in reverse and reversing the result.

Step 3: Optimized Solution (8 minutes)

Use a monotonic stack (decreasing order). Traverse from right to left: for each building, pop all buildings from the stack that are shorter than or equal to the current building (they’re blocked). If the stack is empty after popping, the current building has an ocean view. Push the current building onto the stack. Alternatively, traverse right to left maintaining maximum height, and collect indices of buildings taller than the maximum. Reverse the result to get increasing order. This achieves O(n) time with O(n) space in worst case. The key insight is that a building has an ocean view if and only if no building to its right is taller, which can be determined by tracking the maximum height seen from right to left.

Solution Approaches

The key insight is that a building has an ocean view if it’s taller than all buildings to its right. We can solve this by:

Iterating from right to left: Start from the rightmost building and track the maximum height seen so far
Track maximum height: If current building is taller than or equal to the maximum height seen, it has an ocean view
Reverse result: Since we iterate right-to-left, reverse the result to get indices in increasing order

Solution 1: Simple Greedy (Recommended)

Time Complexity: O(n)
Space Complexity: O(1) excluding output array

The simplest and most efficient approach: iterate from right to left, tracking the maximum height seen so far.

class Solution {
public:
    vector<int> findBuildings(vector<int>& heights) {
        int n = heights.size();
        vector<int> rtn;
        int maxHeight = -1;
        
        for (int curr = n - 1; curr >= 0; curr--) {
            if (maxHeight < heights[curr]) {
                rtn.push_back(curr);
                maxHeight = heights[curr];
            }
        }
        
        reverse(rtn.begin(), rtn.end());
        return rtn;
    }
};

How it works:

Start from the rightmost building (index n-1)
Track maxHeight - the maximum height seen so far
If current building is taller than maxHeight, it has an ocean view
Update maxHeight to the current building’s height
Reverse the result to get indices in increasing order

Why this works:

A building has an ocean view if it’s taller than all buildings to its right
By iterating right-to-left, we can check this condition efficiently
We only need to track the maximum height, not all buildings

Solution 2: Monotonic Stack

Time Complexity: O(n)
Space Complexity: O(n) for the stack

Uses a monotonic stack to maintain buildings in decreasing order of height.

class Solution {
public:
    vector<int> findBuildings(vector<int>& heights) {
        int n = heights.size();
        vector<int> rtn;
        stack<int> stk;
        
        for (int curr = n - 1; curr >= 0; curr--) {
            // Remove buildings that are shorter than current
            while (!stk.empty() && heights[stk.top()] < heights[curr]) {
                stk.pop();
            }
            
            // If stack is empty, current building has ocean view
            if (stk.empty()) {
                rtn.push_back(curr);
            }
            
            stk.push(curr);
        }
        
        reverse(rtn.begin(), rtn.end());
        return rtn;
    }
};

How it works:

Iterate from right to left
Use a stack to maintain indices of buildings that could block the view
Pop buildings from stack that are shorter than current building
If stack is empty after popping, current building has ocean view
Push current building index to stack

Why this works:

Stack maintains buildings in decreasing order of height
If a building is shorter than current, it can’t block current’s view
If stack is empty, no building to the right can block current’s view

How the Algorithm Works

Key Insight: Right-to-Left Iteration

Problem: For each building, check if all buildings to its right are shorter.

Solution: Iterate from right to left, tracking the maximum height seen so far.

Why right-to-left:

We need to know the maximum height of all buildings to the right
By iterating right-to-left, we can maintain this information efficiently
Each building only needs to compare with the maximum height seen so far

Step-by-Step Example: `heights = [4,2,3,1]`

Initial: maxHeight = -1, rtn = []

i = 3: heights[3] = 1
  maxHeight = -1 < 1 → has ocean view
  rtn = [3], maxHeight = 1

i = 2: heights[2] = 3
  maxHeight = 1 < 3 → has ocean view
  rtn = [3, 2], maxHeight = 3

i = 1: heights[1] = 2
  maxHeight = 3 >= 2 → no ocean view
  rtn = [3, 2], maxHeight = 3

i = 0: heights[0] = 4
  maxHeight = 3 < 4 → has ocean view
  rtn = [3, 2, 0], maxHeight = 4

After reverse: rtn = [0, 2, 3]

Visual Representation:

Buildings: [4, 2, 3, 1]
Indices:    0  1  2  3
            │  │  │  │
            │  │  └──┴──> Ocean
            │  │     │
            │  └─────┼──> Blocked by building 2
            └────────┼──> Ocean view (tallest)
                     │
            Ocean view: [0, 2, 3]

Step-by-Step Example: `heights = [1,3,2,4]`

Initial: maxHeight = -1, rtn = []

i = 3: heights[3] = 4
  maxHeight = -1 < 4 → has ocean view
  rtn = [3], maxHeight = 4

i = 2: heights[2] = 2
  maxHeight = 4 >= 2 → no ocean view
  rtn = [3], maxHeight = 4

i = 1: heights[1] = 3
  maxHeight = 4 >= 3 → no ocean view
  rtn = [3], maxHeight = 4

i = 0: heights[0] = 1
  maxHeight = 4 >= 1 → no ocean view
  rtn = [3], maxHeight = 4

After reverse: rtn = [3]

Algorithm Breakdown

Solution 1: Simple Greedy

vector<int> findBuildings(vector<int>& heights) {
    int n = heights.size();
    vector<int> rtn;
    int maxHeight = -1;
    
    for (int curr = n - 1; curr >= 0; curr--) {
        if (maxHeight < heights[curr]) {
            rtn.push_back(curr);
            maxHeight = heights[curr];
        }
    }
    
    reverse(rtn.begin(), rtn.end());
    return rtn;
}

Key Points:

Right-to-left iteration: Start from the rightmost building
Track maximum: Maintain maximum height seen so far
Compare and update: If current is taller, add to result and update max
Reverse result: Get indices in increasing order

Solution 2: Monotonic Stack

vector<int> findBuildings(vector<int>& heights) {
    int n = heights.size();
    vector<int> rtn;
    stack<int> stk;
    
    for (int curr = n - 1; curr >= 0; curr--) {
        while (!stk.empty() && heights[stk.top()] < heights[curr]) {
            stk.pop();
        }
        
        if (stk.empty()) {
            rtn.push_back(curr);
        }
        
        stk.push(curr);
    }
    
    reverse(rtn.begin(), rtn.end());
    return rtn;
}

Key Points:

Monotonic stack: Maintains buildings in decreasing order
Pop shorter buildings: Remove buildings that can’t block current
Check if empty: Empty stack means no blocking buildings
Push current: Add current building to stack

Complexity Analysis

Approach	Time	Space	Pros	Cons
Simple Greedy	O(n)	O(1)	Simple, efficient, no extra space	-
Monotonic Stack	O(n)	O(n)	More general pattern	Extra space, more complex

Edge Cases

All buildings same height: Only rightmost building has ocean view
- heights = [2,2,2,2] → [3]
Increasing heights: All buildings have ocean view
- heights = [1,2,3,4] → [0,1,2,3]
Decreasing heights: Only leftmost building has ocean view
- heights = [4,3,2,1] → [0,1,2,3] (all have view since all to right are shorter)
Single building: Always has ocean view
- heights = [5] → [0]

Key Insights

Right-to-left iteration: Essential for efficiently checking if buildings to the right are shorter
Track maximum only: We only need the maximum height, not all heights
Greedy approach: Local optimal (taller than max) leads to global optimal
Equal heights: Buildings of equal height block each other (use < not <=)

Common Mistakes

Left-to-right iteration: Can’t efficiently check if buildings to right are shorter
Wrong comparison: Using <= instead of < for equal heights
Forgetting to reverse: Result indices should be in increasing order
Not handling edge cases: Single building, all same height, etc.

Optimization Tips

Use Solution 1: Simpler and more space-efficient
Reserve space: Can reserve space for result vector if needed
Early termination: Not applicable here (need to check all buildings)

739. Daily Temperatures - Similar monotonic stack pattern
496. Next Greater Element I - Monotonic stack
503. Next Greater Element II - Monotonic stack with circular array
42. Trapping Rain Water - Monotonic stack, water trapping
84. Largest Rectangle in Histogram - Monotonic stack

Pattern Recognition

This problem demonstrates the “Monotonic Stack” and “Greedy” patterns:

Iterate from right to left
Track maximum (or use stack) to maintain order
Compare current with tracked value
Update result based on comparison

Real-World Applications

City Planning: Determining which buildings have unobstructed views
Real Estate: Identifying properties with ocean/mountain views
Signal Processing: Finding peaks in signal data
Algorithm Design: Understanding monotonic stack patterns

Why Solution 1 is Better

Advantages of Simple Greedy:

O(1) extra space: Only uses a single variable
Simpler code: Easier to understand and maintain
Same time complexity: O(n) in both cases
More efficient: No stack operations overhead

When to use Monotonic Stack:

Need to track multiple values, not just maximum
Need to answer queries about “next greater/smaller”
Problem requires maintaining order of elements

For this problem, Solution 1 (Simple Greedy) is the optimal choice.

This problem demonstrates the importance of choosing the right direction for iteration and the power of simple greedy approaches over more complex data structures when the problem allows it.

Robina Li

[Medium] 1762. Buildings With an Ocean View

[Medium] 1762. Buildings With an Ocean View

Examples

Constraints

Clarification Questions

Interview Deduction Process (20 minutes)

Solution Approaches

Solution 1: Simple Greedy (Recommended)

Solution 2: Monotonic Stack

How the Algorithm Works

Key Insight: Right-to-Left Iteration

Step-by-Step Example: `heights = [4,2,3,1]`

Step-by-Step Example: `heights = [1,3,2,4]`

Algorithm Breakdown

Solution 1: Simple Greedy

Solution 2: Monotonic Stack

Complexity Analysis

Edge Cases

Key Insights

Common Mistakes

Optimization Tips

Pattern Recognition

Real-World Applications

Why Solution 1 is Better

Related Posts

Recent Posts

[Medium] 1762. Buildings With an Ocean View

Examples

Constraints

Clarification Questions

Interview Deduction Process (20 minutes)

Solution Approaches

Solution 1: Simple Greedy (Recommended)

Solution 2: Monotonic Stack

How the Algorithm Works

Key Insight: Right-to-Left Iteration

Step-by-Step Example: heights = [4,2,3,1]

Step-by-Step Example: heights = [1,3,2,4]

Algorithm Breakdown

Solution 1: Simple Greedy

Solution 2: Monotonic Stack

Complexity Analysis

Edge Cases

Key Insights

Common Mistakes

Optimization Tips

Related Problems

Pattern Recognition

Real-World Applications

Why Solution 1 is Better

Related Posts

Recent Posts

Step-by-Step Example: `heights = [4,2,3,1]`

Step-by-Step Example: `heights = [1,3,2,4]`