LC 1762 [M] Buildings With an Ocean View - ALawliet/algorithms GitHub Wiki

• the rightmost building always has an ocean view and we need to keep track of the tallest building so far
• go backwards from right to left to check if any other buildings to the left can see above the last building with an ocean view which has the max height
• since we iterated backwards we should use a deque to append to the front to get the correct order

where res is the list of of indexes of buildings that can see the ocean on the right, and we add to it when there are no buildings taller than it from the right

the key observation if that if there is a building taller than cur to the right, it blocks that cur building and everything to its left

class Solution:
    def findBuildings(self, heights: List[int]) -> List[int]:
        # init with the last
        tallest = heights[-1]
        res = deque([ len(heights)-1 ])
        # print(res)

        for r in range(len(heights) - 2, -1, -1): # loop reverse from 2nd to last
            # print(r, heights[r])
            if heights[r] <= tallest: # just do heights[i] > tallest... 
                continue
            else: # we found a taller building on the left
                res.appendleft(r)
                tallest = heights[r]
        return res

class Solution:
    def findBuildings(self, heights: List[int]) -> List[int]:
        n = len(heights)
        res = deque([n-1])
        maxHeight = heights[n-1]
        r = n - 2
        while r >= 0:
            if heights[r] > maxHeight:
                res.appendleft(r)
                maxHeight = heights[r]
            r -= 1
        return res

we don't actually need to 2 variables res and tallest/maxHeight we can get rid of the tallest variable because the latest element added to res is the significant blocker so far

class Solution:
    def findBuildings(self, heights: List[int]) -> List[int]:
        n = len(heights)
        res = deque( [n-1] )

        r = n-2
        while r >= 0:
            if heights[r] > heights[res[0]]: # leftmost
                res.appendleft(r)
            r -= 1

        return res

class Solution:
    def findBuildings(self, heights: List[int]) -> List[int]:
        res = [n-1]
        for i in range(n-2, -1, -1):
            if heights[i] > heights[res[-1]]: # rightmost
                res.append(i)
        res.reverse()
        return res

class Solution:
    def findBuildings(self, heights: List[int]) -> List[int]:
        n = len(heights)
        idx_see_ocean = deque([n-1])
        for r in range(n-2, -1, -1):
            if heights[r] > heights[i_see_ocean[0]]: # leftmost
                idx_see_ocean.appendleft(r)
        return idx_see_ocean