Is Buildings With an Ocean View easy or hard?

Buildings With an Ocean View is classified as Medium difficulty on LeetCode. The logic becomes simple once you recognize that scanning from right to left eliminates repeated comparisons and reduces the complexity from O(n²) to O(n).

Buildings With an Ocean View Python/Java solution

The typical Python or Java solution performs a reverse traversal of the heights array, keeps track of the tallest building seen so far, and records indices that exceed that height. The final list is reversed to return indices in increasing order.

How to solve Buildings With an Ocean View in O(n)?

Iterate through the buildings from the rightmost index to the left. Maintain a variable storing the maximum height encountered so far. If the current building is taller than this value, it has an ocean view and you add its index to the result, then update the maximum height.

What is the best approach for Buildings With an Ocean View?

The most efficient solution scans the array from right to left while tracking the maximum height seen so far. A building has an ocean view if its height is greater than this running maximum. This approach runs in O(n) time and O(1) extra space, making it the preferred interview solution.

Is Buildings With an Ocean View asked at Google/Amazon/Meta?

Buildings With an Ocean View (LeetCode 1762) is commonly reported in Meta interviews and appears in preparation lists for other big tech companies. It tests array traversal patterns and recognition of monotonic stack concepts.

What data structure is used in Buildings With an Ocean View?

The optimal implementation only needs a running maximum variable and the result list. Conceptually, the problem relates to a monotonic decreasing stack pattern, which appears in many visibility and next-greater-element problems.

What is the time complexity of Buildings With an Ocean View?

The optimal solution runs in O(n) time because the array is traversed exactly once from right to left. Each building is compared with the current maximum height. Space complexity is O(1) excluding the result array that stores the visible building indices.

Description Hints 2 Solution Video 6:51

1762. Buildings With an Ocean View

Medium80.9% acceptance5 companiesPremium elsewhere, free here

There are n buildings in a line. You are given an integer array heights of size n that represents the heights of the buildings in the line.

The ocean is to the right of the buildings. A building has an ocean view if the building can see the ocean without obstructions. Formally, a building has an ocean view if all the buildings to its right have a smaller height.

Return a list of indices (0-indexed) of buildings that have an ocean view, sorted in increasing order.

Example 1:

Input: heights = [4,2,3,1]
Output: [0,2,3]
Explanation: Building 1 (0-indexed) does not have an ocean view because building 2 is taller.

Example 2:

Input: heights = [4,3,2,1]
Output: [0,1,2,3]
Explanation: All the buildings have an ocean view.

Example 3:

Input: heights = [1,3,2,4]
Output: [3]
Explanation: Only building 3 has an ocean view.

Constraints:

1 <= heights.length <= 10⁵
1 <= heights[i] <= 10⁹

Asked at 5 companies

Meta Anduril Amazon

Google Microsoft

Topics

Hints open one at a time

Hint 1

You can traverse the buildings from the nearest to the ocean to the furthest.

Hint 2

Keep with you the maximum to the right while traversing to determine if you can see the ocean or not.

6:51

Still stuck?Read the written solution, or watch a walkthrough.

Open solution