Problem Description

You have n buildings arranged in a line from left to right. Each building has a specific height given in an array heights of size n.

The ocean is located to the right of all buildings. A building has an "ocean view" if it can see the ocean without any obstructions. This means a building can see the ocean only if all the buildings to its right are shorter than it is.

Your task is to find all buildings that have an ocean view and return their indices (0-indexed) in increasing order.

For example, if heights = [4, 2, 3, 1]:

• Building at index 0 (height 4) can see the ocean because all buildings to its right (2, 3, 1) are shorter
• Building at index 1 (height 2) cannot see the ocean because building at index 2 (height 3) is taller
• Building at index 2 (height 3) can see the ocean because the only building to its right (1) is shorter
• Building at index 3 (height 1) can always see the ocean as it's the rightmost building

The answer would be [0, 2, 3].

The solution works by traversing the array from right to left, keeping track of the maximum height seen so far. Any building taller than this maximum can see the ocean, so we add its index to our result. We then update the maximum and continue. Finally, we reverse the result to get indices in increasing order.

Intuition

The key insight is to think about what determines whether a building can see the ocean. A building can see the ocean if and only if there's no taller building to its right blocking the view.

If we start from the rightmost building, it always has an ocean view since there's nothing to its right. As we move leftward, we only need to track the tallest building we've seen so far on the right side.

Why? Because if a building is taller than the maximum height on its right, it means it's taller than ALL buildings on its right - guaranteeing an ocean view. If it's not taller than the maximum, then at least one building on the right blocks its view.

This leads us to a simple approach: traverse from right to left, maintaining a running maximum mx. For each building at position i:

• If heights[i] > mx, this building has an ocean view (add index i to result)
• Update mx to be max(mx, heights[i]) for the next iteration

Since we're traversing right to left but need to return indices in increasing order, we reverse the result at the end.

This approach is efficient because we only need one pass through the array and we make the decision for each building based on a single comparison with the running maximum.

Learn more about Stack and Monotonic Stack patterns.

Solution Approach

We implement the solution using a reverse traversal approach to find buildings with an ocean view.

Algorithm Steps:

1. Initialize variables:

   • Create an empty list ans to store the indices of buildings with ocean view
   • Set mx = 0 to track the maximum height seen so far from the right

2. Traverse from right to left:

   • Use a loop: for i in range(len(heights) - 1, -1, -1) to iterate from the last index to the first
   • For each building at index i:
     • Compare heights[i] with mx
     • If heights[i] > mx, this building can see the ocean:
       • Append index i to ans
       • Update mx = heights[i] as this becomes the new maximum for buildings to the left
     • If heights[i] <= mx, skip this building as it's blocked

3. Return the result:

   • Since we traversed from right to left, ans contains indices in decreasing order
   • Return ans[::-1] to reverse the list and get indices in increasing order

Example walkthrough with heights = [4, 2, 3, 1]:

• Start from index 3: heights[3] = 1 > 0 → Add 3 to ans, update mx = 1
• Move to index 2: heights[2] = 3 > 1 → Add 2 to ans, update mx = 3
• Move to index 1: heights[1] = 2 < 3 → Skip (blocked by building at index 2)
• Move to index 0: heights[0] = 4 > 3 → Add 0 to ans, update mx = 4
• ans = [3, 2, 0] → Reverse to get [0, 2, 3]

Time Complexity: O(n) - single pass through the array
Space Complexity: O(1) extra space (excluding the output array)

Example Walkthrough

Let's walk through the solution with heights = [5, 3, 4, 2, 6, 1].

We'll traverse from right to left, tracking the maximum height seen so far to determine which buildings have an ocean view.

Initial Setup:

• ans = [] (to store indices with ocean view)
• mx = 0 (maximum height seen from the right)

Step-by-step traversal:

i = 5 (heights[5] = 1):

• Is 1 > 0? Yes! Building 5 can see the ocean
• Add index 5 to ans: ans = [5]
• Update mx: mx = 1

i = 4 (heights[4] = 6):

• Is 6 > 1? Yes! Building 4 can see the ocean
• Add index 4 to ans: ans = [5, 4]
• Update mx: mx = 6

i = 3 (heights[3] = 2):

• Is 2 > 6? No. Building 3 is blocked by building 4
• Skip this building
• mx remains 6

i = 2 (heights[2] = 4):

• Is 4 > 6? No. Building 2 is blocked by building 4
• Skip this building
• mx remains 6

i = 1 (heights[1] = 3):

• Is 3 > 6? No. Building 1 is blocked by building 4
• Skip this building
• mx remains 6

i = 0 (heights[0] = 5):

• Is 5 > 6? No. Building 0 is blocked by building 4
• Skip this building
• mx remains 6

Final Step:

• Current ans: [5, 4] (in reverse order)
• Reverse to get increasing order: [4, 5]

Result: Buildings at indices 4 and 5 have an ocean view.

This makes sense because:

• Building 4 (height 6) is the tallest and can see over building 5 (height 1)
• Building 5 (height 1) is rightmost, so it always has an ocean view
• All other buildings are blocked by the tall building at index 4

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the heights array. The algorithm iterates through the array exactly once from right to left (from index n-1 to 0), performing constant-time operations (comparison and append) at each step.

The space complexity is O(1) if we exclude the space used for the output array ans. The only additional space used is the variable mx which stores the maximum height seen so far, requiring constant space. Including the output array, the space complexity would be O(k) where k is the number of buildings that can see the ocean, but following the convention of not counting the space required for the output, we consider it as O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Reverse the Result

The Pitfall: Since we traverse from right to left, indices are naturally collected in descending order. A common mistake is forgetting to reverse the result before returning, which would give incorrect output.

Incorrect Implementation:

def findBuildings(self, heights: List[int]) -> List[int]:
    result = []
    max_height_so_far = 0
  
    for index in range(len(heights) - 1, -1, -1):
        if heights[index] > max_height_so_far:
            result.append(index)
            max_height_so_far = heights[index]
  
    return result  # Wrong! Returns [3, 2, 0] instead of [0, 2, 3]

Solution: Always remember to reverse the result with return result[::-1] when using right-to-left traversal.

2. Using >= Instead of > for Comparison

The Pitfall: Using >= instead of > when comparing with max_height_so_far would incorrectly include buildings that are equal in height to a building on their right.

Incorrect Implementation:

if heights[index] >= max_height_so_far:  # Wrong!
    result.append(index)
    max_height_so_far = heights[index]

Why it's wrong: If heights = [3, 3, 3, 3], using >= would return all indices [0, 1, 2, 3], but only index 3 should have an ocean view since buildings of equal height block the view.

Solution: Use strict inequality > to ensure a building must be strictly taller than all buildings to its right.

3. Incorrect Initialization of Maximum Height

The Pitfall: Initializing max_height_so_far with a non-zero value or the first/last element's height instead of 0.

Incorrect Implementation:

max_height_so_far = heights[-1]  # Wrong initialization!
for index in range(len(heights) - 2, -1, -1):  # Skips last building
    if heights[index] > max_height_so_far:
        result.append(index)
        max_height_so_far = heights[index]

Why it's wrong: This approach incorrectly skips the rightmost building, which always has an ocean view regardless of its height.

Solution: Initialize max_height_so_far = 0 and start the loop from the last index to ensure the rightmost building is properly evaluated.