Buildings With an Ocean View solution and explanation
Google
9 more videos on this problem
BUILDINGS WITH AN OCEAN VIEW | PYTHON | LEETCODE 1762Cracking FAANG · 6:51 · 8K views
Buildings With an Ocean View - Leetcode 1762 - PythonNeetCodeIO · 9:03 · 6K views
Leetcode 1762 | Buildings With an Ocean View (New Problem)AverageLeeter · 19:40 · 2K views
LEETCODE 1762 (JAVASCRIPT) | BUILDINGS WITH AN OCEAN VIEWAndy Gala · 12:01 · 1K views
LeetCode 1762 - Buildings With an Ocean ViewLeetCode Daily · 5:48 · 709 views
Buildings With an Ocean View - LeetCode 1762 - Python #monotonicstackDeepti Talesra · 17:09 · 602 views
Buildings With an Ocean Viewcoding interview questions · 11:33 · 327 views
Buildings With an Ocean View - Leetcode 1762 - PythonLilyCode · 6:41 · 273 views
Stack Solution to LeetCode 1762 - Buildings With Ocean ViewScott Hacks Code · 10:02 · 221 views
1762 Building with an ocean View (Leetcode Premium)CapsLock · 12:53 · 178 views
The problem
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).
class Solution:
def findBuildings(self, heights: List[int]) -> List[int]:
ans = []
mx = 0
for i in range(len(heights) - 1, -1, -1):
if heights[i] > mx:
ans.append(i)
mx = heights[i]
return ans[::-1]class Solution {
public int[] findBuildings(int[] heights) {
int n = heights.length;
List<Integer> ans = new ArrayList<>();
int mx = 0;
for (int i = heights.length - 1; i >= 0; --i) {
if (heights[i] > mx) {
ans.add(i);
mx = heights[i];
}
}
Collections.reverse(ans);
return ans.stream().mapToInt(Integer::intValue).toArray();
}
}class Solution {
public:
vector<int> findBuildings(vector<int>& heights) {
vector<int> ans;
int mx = 0;
for (int i = heights.size() - 1; ~i; --i) {
if (heights[i] > mx) {
ans.push_back(i);
mx = heights[i];
}
}
reverse(ans.begin(), ans.end());
return ans;
}
};/**
* @param {number[]} heights
* @return {number[]}
*/
var findBuildings = function (heights) {
const ans = [];
let mx = 0;
for (let i = heights.length - 1; ~i; --i) {
if (heights[i] > mx) {
ans.push(i);
mx = heights[i];
}
}
return ans.reverse();
};function findBuildings(heights: number[]): number[] {
const ans: number[] = [];
let mx = 0;
for (let i = heights.length - 1; ~i; --i) {
if (heights[i] > mx) {
ans.push(i);
mx = heights[i];
}
}
return ans.reverse();
}func findBuildings(heights []int) (ans []int) {
mx := 0
for i := len(heights) - 1; i >= 0; i-- {
if v := heights[i]; v > mx {
ans = append(ans, i)
mx = v
}
}
for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
ans[i], ans[j] = ans[j], ans[i]
}
return
}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 |
Frequently asked questions
Is Buildings With an Ocean View easy or hard?
Buildings With an Ocean View is classified as Medium difficulty on LeetCode. The logic becomes simple once you recognize that scanning from right to left eliminates repeated comparisons and reduces the complexity from O(n²) to O(n).
Buildings With an Ocean View Python/Java solution
The typical Python or Java solution performs a reverse traversal of the heights array, keeps track of the tallest building seen so far, and records indices that exceed that height. The final list is reversed to return indices in increasing order.
How to solve Buildings With an Ocean View in O(n)?
Iterate through the buildings from the rightmost index to the left. Maintain a variable storing the maximum height encountered so far. If the current building is taller than this value, it has an ocean view and you add its index to the result, then update the maximum height.
What is the best approach for Buildings With an Ocean View?
The most efficient solution scans the array from right to left while tracking the maximum height seen so far. A building has an ocean view if its height is greater than this running maximum. This approach runs in O(n) time and O(1) extra space, making it the preferred interview solution.
Is Buildings With an Ocean View asked at Google/Amazon/Meta?
Buildings With an Ocean View (LeetCode 1762) is commonly reported in Meta interviews and appears in preparation lists for other big tech companies. It tests array traversal patterns and recognition of monotonic stack concepts.
What data structure is used in Buildings With an Ocean View?
The optimal implementation only needs a running maximum variable and the result list. Conceptually, the problem relates to a monotonic decreasing stack pattern, which appears in many visibility and next-greater-element problems.
What is the time complexity of Buildings With an Ocean View?
The optimal solution runs in O(n) time because the array is traversed exactly once from right to left. Each building is compared with the current maximum height. Space complexity is O(1) excluding the result array that stores the visible building indices.