1762. Buildings With an Ocean View

Problem Description

In this problem, we are given an array heights that represents the heights of buildings in a line, with the ocean situated to the right of the last building. The goal is to find out which buildings have an unobstructed view of the ocean. A building has an ocean view if all buildings to its right are shorter than it. We need to return a list of the indices of the buildings that can see the ocean. The list of indices should be sorted in increasing order and needs to be 0-indexed, which means the first building in the line has an index of 0.

Intuition

The solution involves iterating through the list of building heights in reverse (starting from the building farthest from the ocean). As we iterate, we maintain a running maximum height (mx). When the current building's height exceeds this running maximum, it means this building has an ocean view, because there are no taller buildings to its right blocking its view of the ocean.

The steps for the solution are as follows:

• Initialize an empty list ans to store indices of buildings with ocean views.
• Set a variable mx to 0 to keep track of the maximum height seen so far as we iterate backwards.
• Loop through the heights array in reverse order (from last to first):
  • Check if the current building's height is greater than mx, which is the tallest building observed to the right side of the current building.
  • If it is, the current building has an ocean view. We then:
    • Append the index i of this building to the ans list.
    • Update the mx to the new maximum height.
• Since we filled ans in reverse order, we reverse it once more before returning to give the correct order of indices (from left to right).

By iterating from the end towards the beginning, we ensure that the mx reflects the tallest building's height to the right of the current building. This way, each building is checked against only the relevant taller buildings that could potentially block its ocean view.

Learn more about Stack and Monotonic Stack patterns.

Solution Approach

The solution approach can be broken down into the following steps:

• We initialize an empty list ans that will eventually contain the indices of the buildings with an ocean view.
• Define a variable mx to keep track of the maximum height encountered as we iterate through the list of buildings in reverse. This is initially set to 0.
• We start a loop that iterates through the heights array from the last element (furthest from the ocean) towards the first element (closest to the ocean).
• During each step of the loop, we compare the current building's height to mx. If the current height is greater, it means that this building has an unobstructed ocean view since all buildings to its right are shorter.
• If the building has an ocean view, we append its index to the ans list and update mx to the current building's height, ensuring that mx always represents the tallest building encountered so far.
• After iterating through all buildings, we reverse the ans list since we appended indices starting from the building closest to the ocean to get them sorted in the correct (increasing) order. The reasoning for this post-reversal is that indices are collected in decreasing order during the iteration from last to first.

This approach takes advantage of a simple greedy algorithm pattern, which, in this case, means that we always update our 'greedy' choice (mx) to reflect the tallest encountered building so far. The mx effectively "forgets" shorter buildings since they don't impact future comparisons.

In terms of data structures, only a simple list is used to keep track of the indices of buildings with an ocean view. The use of a list also allows us to efficiently reverse its contents at the end of our iteration.

Algorithm Complexity: The time complexity of this solution is O(n), where n is the number of buildings. This is because we have to iterate through all the buildings at least once. The space complexity is also O(n) in the worst case, which occurs when all buildings have an ocean view, and we need a list of the same length as the input to store the indices.

The solution code utilizing this approach looks like this:

1class Solution:
2    def findBuildings(self, heights: List[int]) -> List[int]:
3        ans = []
4        mx = 0
5        for i in range(len(heights) - 1, -1, -1):
6            if heights[i] > mx:
7                ans.append(i)
8                mx = heights[i]
9        return ans[::-1]

This code translates the approach described above into Python, taking advantage of the language's list and loop constructs to efficiently solve the problem.

Example Walkthrough

Let's apply the solution approach to a small example. Consider the following array of building heights:

1heights = [4, 2, 3, 1]

We want to find out which buildings have an unobstructed view of the ocean. Our ocean is to the right, so we need to see which buildings are not blocked by buildings of greater height to their right.

We start by initializing an empty list ans to store indices and a variable mx with a value of 0 to keep track of the maximum height we've seen so far.

Then we iterate backwards through the array:

1. We start with the last building (index 3), height is 1. mx is 0. Since 1 > 0, we add index 3 to ans and update mx to 1.
2. Move to the next building (index 2), height is 3. Now, 3 > 1 (current mx), so we add this index (2) to ans and update mx to 3.
3. The next building's height (index 1) is 2. Because 2 is not greater than 3 (current mx), we don't do anything.
4. We now reach the first building (index 0), height is 4. Since 4 > 3, we add index 0 to ans and update mx to 4.

After iterating through the array, ans is [0, 2, 3]. However, this is in reverse order, so we reverse it to [3, 2, 0].

Buildings at indices 3, 2, and 0 have an unobstructed view of the ocean. The result is sorted in increasing order, as required by the problem statement.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the given code can be determined by analyzing the loop that iterates in reverse through the list of heights. Since the loop runs exactly once for each element in the heights array, which has n elements, this gives us a time complexity of O(n) where n is the length of the heights array.

Space Complexity

The space complexity of the code is mainly due to the ans list which stores the indices of buildings with an unobstructed view. In the worst case, all buildings can see the ocean, so the space taken by the ans list can be n in the worst case. Thus, the space complexity is O(n). Also, note that this does not account for the space used to store the input heights as that is not part of the space used by the algorithm itself.

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