Your Dashboard
Interview Coaching
Learn
System Design
ML System Design
Code
Behavioral
Salary Negotiation
Interview Guides
Leetcode 1762. Buildings With an Ocean View
Given an array of building heights, return the indices of buildings that have an unobstructed view to the ocean on the right (i.e., no building of equal or greater height between them and the edge). This is typically solved by a right-to-left scan or a monotonic decreasing stack that tracks the current maximum height.
Asked at:
Meta
DESCRIPTION
Given an array of building heights, return the indices of buildings that have an unobstructed view to the ocean on the right (i.e., no building of equal or greater height between them and the edge). This is typically solved by a right-to-left scan or a monotonic decreasing stack that tracks the current maximum height.
Input:
Output:
Explanation: Building 0 (height 4) is taller than all buildings to its right (2, 3, 1). Building 2 (height 3) is taller than building 3 (height 1). Building 3 is at the edge. Building 1 (height 2) is blocked by building 2 (height 3).
Constraints:
- 1 <= heights.length <= 10^5
- 1 <= heights[i] <= 10^9
- Return indices in ascending order
Understanding the Problem
Let's understand what we're being asked to do. We have an array of building heights like [4, 2, 3, 1] and need to find which buildings can see the ocean on the right.
Tracing through: Building at index 0 (height 4) looks right and sees buildings of height 2, 3, 1 - all shorter, so it has an unobstructed view. Building at index 1 (height 2) looks right and sees 3 (taller!) - blocked. Building at index 2 (height 3) looks right and sees only 1 (shorter) - unobstructed view. Building at index 3 (height 1) is at the edge - always has ocean view.
Important constraint: A building has an ocean view if no building to its right is of equal or greater height. The rightmost building always has a view.
Edge cases to consider: What if all buildings are the same height? What if heights are strictly increasing? What if there's only one building? What if the array is empty?
Brute Force Approach
The straightforward approach is to check each building individually: for each building at index i, scan all buildings from i+1 to the end to see if any are equal or taller. If we find a blocking building, mark this building as having no view; otherwise, it has an ocean view. This approach is simple to understand but requires checking every pair of buildings, leading to quadratic time complexity.
Start ocean view buildings algorithm (brute force)
0 / 32
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n²) For each of n buildings, we potentially scan through all remaining buildings to the right, resulting in n*(n-1)/2 comparisons in the worst case
Space Complexity: O(1) We only use a constant amount of extra space for loop counters and the result array (output doesn't count toward space complexity)
Building Intuition
A building can see the ocean if and only if it's taller than all buildings to its right.
This means if we scan from right to left, we can track the maximum height seen so far. Any building taller than this maximum has an unobstructed view!
By scanning right-to-left and maintaining the current maximum, we can determine in a single pass whether each building has an ocean view.
This transforms what could be an O(n²) problem (checking all buildings to the right of each building) into an O(n) solution with just one traversal!
Imagine standing at the ocean and looking back at the buildings. The rightmost building is always visible to you.
As you look further left, a building is only visible if it's taller than everything between it and you. This is exactly what 'maximum height to the right' captures - if a building exceeds this maximum, you can see it from the ocean!
Common Mistakes
Optimal Solution
The optimal approach scans the array from right to left while maintaining the maximum height seen so far. Start from the rightmost building (which always has an ocean view) and track the current maximum height. For each building moving left, if its height is greater than the current maximum, it has an unobstructed view - add its index to the result and update the maximum. This single-pass solution efficiently identifies all buildings with ocean views in linear time.
Start finding buildings with ocean view
0 / 17
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n) We make a single pass through the array from right to left, checking each building exactly once
Space Complexity: O(1) We only need one variable to track the maximum height seen so far, regardless of array size (the result array doesn't count toward space complexity)
What We've Learned
- Right-to-left scan pattern: When determining if elements have an unobstructed view to the right, scan from right-to-left while tracking the maximum seen so far - this single-pass approach naturally identifies all qualifying elements because you're moving from the reference point (ocean) backward.
- Monotonic stack for visibility problems: Use a monotonic decreasing stack to track buildings that can "see" the ocean - each building blocks the view of all shorter buildings behind it, making this a classic next greater element variant where you're finding elements with no greater/equal element to their right.
- Result ordering consideration: Since right-to-left scanning produces indices in reverse order, remember to reverse your result array before returning, or use a deque/insert-at-front strategy to maintain correct left-to-right ordering without an extra reversal step.
- Off-by-one with equality: A critical mistake is using `>` instead of `>=` when comparing heights - buildings with equal height block the view, so a building at index i needs `height[i] > maxRight` to qualify, not just `height[i] >= maxRight`.
- O(n) single-pass efficiency: This solution achieves O(n) time with O(1) extra space (excluding output) because tracking a single maximum value eliminates the need for nested loops - each building is examined exactly once, making it optimal compared to naive O(n²) approaches that check all buildings to the right.
- Visibility and dominance problems: This pattern extends to any problem involving line-of-sight, dominance relationships, or future maximums - stock price analysis (days until higher price), skyline problems, or finding elements that aren't overshadowed by subsequent elements all use this right-to-left maximum tracking technique.
Related Concepts and Problems to Practice
medium
This problem uses a monotonic stack to find the next greater element, which is conceptually very similar to finding buildings with ocean views. Both require tracking elements and comparing them against future values in the array.
hard
This problem also uses a monotonic stack to process bars/heights and determine visibility relationships. Like the ocean view problem, it requires maintaining a stack of indices while comparing heights and determining which elements remain visible.
Test Your Understanding
Why is bars the right data structure for this problem?
bars provides the optimal access pattern
It's the only data structure that works
It's the easiest to implement
It uses the least memory
Select an answer to see the explanation
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late October, 2025
Meta
Senior
Late October, 2025
Meta
Senior
Mid October, 2025
Meta
Senior
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.