Leetcode 1762. Buildings With an Ocean View

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?

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.

def ocean_view_buildings(heights):
    """
    Find buildings with unobstructed ocean view (brute force).
    For each building, check all buildings to its right.
    """
    result = []
    n = len(heights)
    
    # Check each building
    for i in range(n):
        has_view = True
        
        # Check all buildings to the right
        for j in range(i + 1, n):
            # If any building to the right is >= current height
            if heights[j] >= heights[i]:
                has_view = False
                break
        
        # If no blocking building found, add to result
        if has_view:
            result.append(i)
    
    return result

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!

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.

def ocean_view_buildings(heights):
    """
    Find buildings with unobstructed ocean view on the right.
    Scan right-to-left, tracking maximum height seen.
    """
    result = []
    max_height = 0
    
    # Scan from right to left
    for i in range(len(heights) - 1, -1, -1):
        current_height = heights[i]
        
        # If current building is taller than max, it has ocean view
        if current_height > max_height:
            result.append(i)
            max_height = current_height
    
    # Reverse to get left-to-right order
    result.reverse()
    return result

• 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.