LeetCode Problem 1762

Difficulty: 🟡 Medium
Topics: Array, Stack, Monotonic Stack

Solution

LeetCode 1762, Buildings With an Ocean View

Problem Understanding

This problem gives us an array called heights, where each element represents the height of a building. The buildings are arranged in a straight line from left to right, and the ocean is located to the right side of the last building.

A building has an ocean view if every building to its right is strictly shorter. If there exists even one building to the right with height greater than or equal to the current building, then the current building's view is blocked.

The task is to return the indices of all buildings that can see the ocean. The returned indices must be sorted in increasing order.

For example, given:

heights = [4,2,3,1]

Building 0 has height 4. Every building to its right has smaller height, so it has an ocean view.

Building 1 has height 2. Building 2 has height 3, which blocks the view, so building 1 does not qualify.

Building 2 has height 3. The only building to its right is height 1, so it qualifies.

Building 3 is the rightmost building, so it always has an ocean view.

The answer is:

[0,2,3]

The constraints are important:

• 1 <= heights.length <= 10^5
• 1 <= heights[i] <= 10^9

The array can contain up to one hundred thousand buildings, so an inefficient quadratic solution may become too slow. Heights can also be very large, which means we should avoid assumptions about small value ranges or frequency counting.

Several edge cases are important:

• A single building always has an ocean view.
• Strictly decreasing heights mean every building has an ocean view.
• Strictly increasing heights mean only the last building qualifies.
• Equal heights matter because the condition requires strictly smaller buildings to the right. If two buildings have the same height, the left one does not have an ocean view.
• Very large inputs require an O(n) solution for good performance.

Approaches

Brute Force Approach

The most direct solution is to check every building independently.

For each building i, we scan all buildings to its right. If we ever find a building with height greater than or equal to heights[i], then building i does not have an ocean view.

If no such building exists, we add i to the result.

This approach is correct because it directly implements the definition of an ocean view. However, it is inefficient for large inputs because every building may compare against almost every other building.

In the worst case, this leads to roughly:

1 + 2 + 3 + ... + (n-1)

comparisons, which is O(n^2) time complexity.

With n = 10^5, this is too slow.

Optimal Approach

The key observation is that a building only needs to know the maximum height among buildings to its right.

If we process the array from right to left, we can maintain the tallest building seen so far.

Suppose we are currently examining building i:

• If heights[i] is greater than the maximum height seen to its right, then building i has an ocean view.
• Otherwise, its view is blocked.

After processing building i, we update the running maximum.

This works because scanning from right to left guarantees that the running maximum always represents the tallest building to the right of the current position.

This reduces the complexity to linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1) excluding output	Compare each building with all buildings to its right
Optimal	O(n)	O(1) excluding output	Traverse from right to left while tracking maximum height

Algorithm Walkthrough

1. Initialize an empty list called result.

This list will store the indices of buildings that can see the ocean. 2. Initialize a variable called max_height_right to 0.

This variable represents the tallest building encountered so far while scanning from right to left. 3. Traverse the array from the last index down to the first index.

We move from right to left because the ocean is on the right side. This allows us to know all buildings to the right of the current building. 4. For each building, compare its height with max_height_right.

If the current building's height is strictly greater, then every building to its right is shorter, so this building has an ocean view. 5. If the building qualifies, append its index to result.

Since we are traversing backward, indices are added in reverse order. 6. Update max_height_right.

Set it to the larger value between the current maximum and the current building's height. 7. Reverse the result list before returning it.

This restores the indices to increasing order, as required by the problem.

Why it works

The algorithm maintains an important invariant:

At every step, max_height_right stores the tallest building strictly to the right of the current position.

If the current building is taller than this value, then every building to its right is smaller, which exactly matches the ocean view condition.

Because the invariant is always maintained during the reverse traversal, every qualifying building is correctly identified.

Python Solution

from typing import List

class Solution:
    def findBuildings(self, heights: List[int]) -> List[int]:
        result = []
        max_height_right = 0

        for index in range(len(heights) - 1, -1, -1):
            if heights[index] > max_height_right:
                result.append(index)

            max_height_right = max(max_height_right, heights[index])

        result.reverse()
        return result

The implementation starts by creating an empty result list and a variable called max_height_right.

The loop iterates backward through the array using:

range(len(heights) - 1, -1, -1)

This starts at the last index and moves toward index 0.

Inside the loop, we check whether the current building is taller than every building previously seen on the right side. Since max_height_right stores the tallest right-side building, the comparison:

heights[index] > max_height_right

directly determines whether the building has an ocean view.

If the condition is true, the index is added to result.

Next, we update max_height_right so future iterations correctly know the tallest building to the right.

Finally, because indices were collected in reverse order, we reverse the result list before returning it.

Go Solution

func findBuildings(heights []int) []int {
    result := []int{}
    maxHeightRight := 0

    for i := len(heights) - 1; i >= 0; i-- {
        if heights[i] > maxHeightRight {
            result = append(result, i)
        }

        if heights[i] > maxHeightRight {
            maxHeightRight = heights[i]
        }
    }

    // Reverse result
    left, right := 0, len(result)-1
    for left < right {
        result[left], result[right] = result[right], result[left]
        left++
        right--
    }

    return result
}

The Go solution follows the same logic as the Python implementation.

One difference is that Go does not provide a built in list reversal method, so we reverse the slice manually using a two pointer swap approach.

Go slices dynamically grow as elements are appended, similar to Python lists.

There are no integer overflow concerns here because the constraints fit comfortably within Go's standard int type on modern systems.

Worked Examples

Example 1

heights = [4,2,3,1]

We process from right to left.

Step	Index	Height	max_height_right Before	Ocean View?	Result	max_height_right After
1	3	1	0	Yes	[3]	1
2	2	3	1	Yes	[3,2]	3
3	1	2	3	No	[3,2]	3
4	0	4	3	Yes	[3,2,0]	4

After reversing:

[0,2,3]

Example 2

heights = [4,3,2,1]

Step	Index	Height	max_height_right Before	Ocean View?	Result	max_height_right After
1	3	1	0	Yes	[3]	1
2	2	2	1	Yes	[3,2]	2
3	1	3	2	Yes	[3,2,1]	3
4	0	4	3	Yes	[3,2,1,0]	4

After reversing:

[0,1,2,3]

Example 3

heights = [1,3,2,4]

Step	Index	Height	max_height_right Before	Ocean View?	Result	max_height_right After
1	3	4	0	Yes	[3]	4
2	2	2	4	No	[3]	4
3	1	3	4	No	[3]	4
4	0	1	4	No	[3]	4

After reversing:

[3]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each building is processed exactly once
Space	O(1)	Only a few variables are used, excluding output storage

The algorithm performs a single traversal of the array, making the runtime linear.

The auxiliary space usage is constant because we only maintain the result list and a running maximum variable. The result list itself is required for the output and is not counted as extra space in standard complexity analysis.

Test Cases

from typing import List

class Solution:
    def findBuildings(self, heights: List[int]) -> List[int]:
        result = []
        max_height_right = 0

        for index in range(len(heights) - 1, -1, -1):
            if heights[index] > max_height_right:
                result.append(index)

            max_height_right = max(max_height_right, heights[index])

        result.reverse()
        return result

solution = Solution()

assert solution.findBuildings([4,2,3,1]) == [0,2,3]  # Example 1
assert solution.findBuildings([4,3,2,1]) == [0,1,2,3]  # Strictly decreasing
assert solution.findBuildings([1,3,2,4]) == [3]  # Strictly increasing overall trend

assert solution.findBuildings([1]) == [0]  # Single building
assert solution.findBuildings([2,2,2,2]) == [3]  # Equal heights block views
assert solution.findBuildings([5,1,2,3,4]) == [0,4]  # Tallest at start and end
assert solution.findBuildings([1,2,3,4,5]) == [4]  # Strictly increasing
assert solution.findBuildings([5,4,3,2,1]) == [0,1,2,3,4]  # Strictly decreasing

assert solution.findBuildings([10,7,8,3,6,1]) == [0,2,4,5]  # Mixed pattern
assert solution.findBuildings([1000000000,1,1,1]) == [0,3]  # Very large heights
assert solution.findBuildings([3,1,3,1]) == [2,3]  # Equal height blocking

Test	Why
[4,2,3,1]	Validates the primary example
[4,3,2,1]	Confirms every building qualifies in decreasing order
[1,3,2,4]	Confirms only the tallest rightmost building qualifies
[1]	Tests minimum input size
[2,2,2,2]	Verifies equal heights block visibility
[5,1,2,3,4]	Tests mixed visibility conditions
[1,2,3,4,5]	Validates strictly increasing heights
[5,4,3,2,1]	Validates strictly decreasing heights
[10,7,8,3,6,1]	Tests irregular patterns
[1000000000,1,1,1]	Verifies handling of very large values
[3,1,3,1]	Confirms equal height buildings block earlier ones

Edge Cases

A single building is the simplest possible input. Since there are no buildings to its right, it automatically has an ocean view. A careless implementation might incorrectly initialize comparison values or fail when traversing backward. This solution handles it naturally because the single building is compared against the initial maximum value of 0 and is added to the result.

Equal height buildings are another important edge case. The problem requires all buildings to the right to be strictly smaller. That means equal heights still block the view. For example:

[2,2,2]

Only the last building qualifies. The implementation correctly uses the condition:

heights[index] > max_height_right

instead of >=, which preserves the strict inequality requirement.

Strictly increasing arrays can expose flaws in naive logic. For example:

[1,2,3,4]

Only the last building has an ocean view because every earlier building is blocked by a taller building to its right. The reverse traversal correctly maintains the running maximum and filters out all earlier buildings.

Strictly decreasing arrays are also important because every building qualifies. Some incorrect implementations accidentally remove earlier valid buildings or mishandle ordering. Since every building encountered from right to left is taller than the current maximum, every index is collected and later reversed into the correct increasing order.