NeetCode #770LC-1762MediumGreedy
← Back to All Problems#770 · #1762 · Buildings With an Ocean View(能看到海景的建筑物)
📌 Problem Statement & Constraints
There is a row of buildings with heights
heights, and the ocean is to the right. A building has an ocean view if every building to its right is strictly shorter. Return the indices of such buildings in increasing order. Constraints: 1 <= heights.length <= 10^5, 1 <= heights[i] <= 10^9.💡 Core Algorithmic Approaches
- Scan from right to left, maintaining the maximum height seen so far.
- A building has an ocean view iff its height is strictly greater than that maximum.
- Record its index and update the maximum.
- Reverse the collected indices to return them in increasing order.
💻 Benchmark Python3 Implementation
class Solution:
def findBuildings(self, heights: List[int]) -> List[int]:
res = []
max_h = 0
for i in range(len(heights) - 1, -1, -1):
if heights[i] > max_h: # strictly taller than everything to the right
res.append(i)
max_h = heights[i]
return res[::-1]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one right-to-left pass.
💾 Space Complexity
O(1) beyond the output.
⚠️ Interview Pitfalls & Follow-ups
- Using
>=instead of>: a building equal in height to one to its right is blocked, so the comparison must be strict. - Returning indices in the scan order: the scan is right to left, so reverse before returning.
- Initialising
max_htoheights[-1]: the last building always has a view, so starting at 0 lets it be recorded naturally. - Scanning left to right: you would need to look ahead, which is O(n^2) naively.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.