⚡Flashcard Drill➔
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

  1. Scan from right to left, maintaining the maximum height seen so far.
  2. A building has an ocean view iff its height is strictly greater than that maximum.
  3. Record its index and update the maximum.
  4. 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_h to heights[-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.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems