Buildings With an Ocean View
Understanding the Problem
We have a row of buildings, and the ocean sits to the right. A building can "see" the ocean only if every building between it and the ocean is shorter than it. In other words, no building to the right is as tall or taller.
The rightmost building always has an ocean view since there's nothing blocking it. For every other building, we need to check whether anything to its right is at least as tall. The requirement is "strictly taller", so a building of the same height as its tallest right neighbor does not have an ocean view.
We don't need to compare each building with every building to its right. Whether a building has a view depends on a single value: the maximum height among the buildings to its right. If a building is taller than that maximum, it has an ocean view.
Key Constraints:
1 <= heights.length <= 10^5→ With n up to 100,000, an O(n^2) approach can reach 10 billion comparisons. We want O(n).1 <= heights[i] <= 10^9→ Heights are at least 1, so a running maximum initialized to 0 is always beaten by the first building compared against it. The algorithms only compare heights, never add them, so 32-bit integers are safe.
Approach 1: Brute Force
Intuition
For each building, check every building to its right. If none of them is as tall or taller, that building has an ocean view. This translates the problem statement directly into code: for building i, scan from i+1 to n-1, and stop early as soon as a building with height greater than or equal to heights[i] blocks the view.
Algorithm
- Create an empty result list.
- For each building at index
ifrom left to right: - Set a flag
hasView = true. - For each building at index
jfromi+1to the end: - If
heights[j] >= heights[i], sethasView = falseand break. - If
hasViewis stilltrue, addito the result. - Return the result list.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2). For each of the n buildings, we potentially scan all buildings to its right. In the worst case (strictly decreasing heights), that's n + (n-1) + ... + 1 = O(n^2) comparisons.
- Space Complexity: O(1). We only use a boolean flag and loop variables. The result list is required output.
The waste is in the rescanning: the check for building 0 walks nearly the whole array, and the check for building 1 walks almost the same elements again. A right-to-left pass that carries a running maximum answers the same question for every building with a single comparison.
Approach 2: Right-to-Left Scan with Running Maximum
Intuition
A building has an ocean view if and only if it is taller than every building to its right, which is the same as being taller than the maximum height to its right. Scanning from right to left makes that maximum cheap to maintain: it is the maximum of the heights already visited.
The rightmost building always sees the ocean. Moving left, each building only needs to beat the running maximum, not compare against every individual building between it and the ocean. If it does, it has a view and becomes the new maximum. One detail remains: we collect indices from right to left, so the result must be reversed before returning to satisfy the increasing-order requirement.
Algorithm
- Initialize
maxHeight = 0and an empty result list. - Iterate from the last building to the first (right to left).
- For each building at index
i: - If
heights[i] > maxHeight, this building has an ocean view. Addito the result. - Update
maxHeight = max(maxHeight, heights[i]). - Reverse the result list (since we collected indices right to left, but the output needs increasing order).
- Return the result.
Visualization and Code
Loading animation...
- Time Complexity: O(n). We make a single pass through the array from right to left. Each element is visited exactly once with O(1) work per element. The reversal is also O(n). Total: O(n).
- Space Complexity: O(1). We only use one integer (
maxHeight) as extra space. The result list is required output.
This is already optimal in time and space. But there's an alternative O(n) approach using a monotonic stack that generalizes better to related problems like "next greater element."
Approach 3: Monotonic Stack (Left-to-Right)
Intuition
Instead of scanning right to left, we can scan left to right using a stack. Maintain a stack of building indices that, so far, have an unblocked view. Each new building pops every stacked building whose height is less than or equal to its own, because the new building blocks them. The pop condition is <= rather than < since the problem requires strictly taller: a building of equal height blocks the view too. Whatever remains on the stack after the last building is processed has an ocean view.
Heights on the stack are strictly decreasing from bottom to top, because anything shorter than or equal to an incoming building gets popped before the push. This invariant is why popping can stop at the first taller building: every building below it on the stack is taller still and remains unblocked. When the scan ends, the stack holds exactly the buildings that no later building matched or exceeded, and since indices are pushed left to right, they are already in increasing order.
Algorithm
- Create an empty stack.
- Iterate through buildings from left to right.
- For each building at index
i: - While the stack is not empty and
heights[stack.peek()] <= heights[i], pop from the stack (these buildings are now blocked). - Push
ionto the stack. - The stack now contains the indices of all buildings with an ocean view, in increasing order.
- Convert the stack to an array and return it.
Visualization and Code
Loading animation...
- Time Complexity: O(n). Each building is pushed onto the stack once and popped at most once. Total stack operations: at most 2n. Overall: O(n).
- Space Complexity: O(n). In the worst case (strictly decreasing heights), the stack holds all n indices.