Buildings With an Ocean View - Solution & Explanation
Problem Statement
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.
Example 1:
Input: heights = [4,2,3,1] Output: [0,2,3] Explanation: Building 1 (0-indexed) does not have an ocean view because building 2 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 3 has an ocean view.
Constraints:
1 <= heights.length <= 1051 <= heights[i] <= 109
Approach Overview
Problem Overview: You’re given an array where heights[i] represents the height of the i-th building in a row facing the ocean on the right. A building has an ocean view if every building to its right is strictly shorter. The task is to return the indices of all buildings that can see the ocean.
Approach 1: Brute Force - Check All Buildings to the Right (O(n²) time, O(1) space)
For each building i, scan every building to its right and check whether any height is greater than or equal to heights[i]. If you encounter such a building, the view is blocked. Otherwise, the building has an ocean view and its index is added to the result. This approach uses nested iteration over the array, making it straightforward but inefficient for large inputs.
The key operation is repeatedly comparing heights[i] with every element in the subarray to the right. The worst case happens when the array is strictly decreasing, forcing the inner loop to run for almost every element. Time complexity becomes O(n²) with constant extra memory O(1). This method demonstrates the core visibility rule but rarely passes strict performance constraints in interviews.
Approach 2: Reverse Traversal to Track Maximum Height (O(n) time, O(1) space)
The optimal solution processes buildings from right to left. Maintain a variable maxHeight representing the tallest building seen so far on the right. When iterating backward, if heights[i] is greater than maxHeight, that building has an ocean view because nothing taller exists to its right. Update maxHeight and record the index.
This works because the rightmost building always sees the ocean. As you move left, you only need to compare the current height with the maximum height already observed. The scan happens once, making the time complexity O(n) and space complexity O(1) (excluding the result list).
This logic can also be framed using a monotonic stack. If you iterate left to right, you maintain a decreasing stack of building indices and remove smaller heights when a taller building appears. However, the reverse traversal approach is simpler and avoids explicit stack operations, even though the concept is closely related to a stack-based monotonic structure.
Recommended for interviews: Interviewers expect the O(n) reverse traversal solution. Starting with the brute force approach shows you understand the problem definition. Transitioning to the optimized scan demonstrates awareness of monotonic patterns and how to reduce repeated comparisons by maintaining the maximum height seen so far.
Solution
We traverse the array height in reverse order for each element v, comparing v with the maximum element mx on the right. If mx \lt v, it means all elements to the right are smaller than the current element, so the current position can see the ocean and is added to the result array ans. Then we update mx to v.
After the traversal, return ans in reverse order.
The time complexity is O(n), where n is the length of the array. Ignoring the space consumption of the answer array, the space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
JavaScript
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Right-Side Scan | O(n²) | O(1) | Useful for understanding the visibility rule or when constraints are very small |
| Reverse Traversal with Max Tracking | O(n) | O(1) | Best general solution; single pass from right to left with constant extra memory |
| Monotonic Stack | O(n) | O(n) | Useful when solving related problems that require maintaining a decreasing stack structure |
Video Solution
BUILDINGS WITH AN OCEAN VIEW | PYTHON | LEETCODE 1762 • Cracking FAANG • 8,263 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Buildings With an Ocean View easy or hard?
Buildings With an Ocean View Python/Java solution
How to solve Buildings With an Ocean View in O(n)?
What is the best approach for Buildings With an Ocean View?
Is Buildings With an Ocean View asked at Google/Amazon/Meta?
What data structure is used in Buildings With an Ocean View?
What is the time complexity of Buildings With an Ocean View?
Ready to solve this problem?
Practice Buildings With an Ocean View with our built-in code editor and test cases.
Practice on FleetCode