Interview Question: Buildings With an Ocean View (LeetCode 1762). Given an array of building heights, identify the indices of buildings that have an unobstructed view of the ocean to their right. A building has a view if it is strictly taller than all buildings to its right.
Anonymous
I identified this as a variation of the Next Greater Element (NGE) problem. I explained that a building has a view if there is no taller building to its right. I used a Monotonic Decreasing Stack to solve this: as we iterate through the buildings from left to right, whenever we encounter a building taller than or equal to the building at the top of the stack, we pop from the stack because the new building blocks its view. The indices remaining in the stack at the end represent the buildings with an ocean view. This approach runs in O(N) time and O(N) space.
Check out your Company Bowl for anonymous work chats.