Leetcode 1762: Buildings with an ocean view

Iteration starts from the ocean side and moves inward; monotonic stack

2 min readAug 27, 2023

Important trick: Starting from the side where the ocean is and move inwards

Because the building closest to the ocean always has an ocean view, it gives us (1) a reference height to start with and (2) one default element in the output.

As we move from the ocean side inward, this reference height updates. It holds a threshold height that each subsequent building must exceed in order to have an ocean view. And whenever we encounter a building that does have an ocean view, it becomes the new reference height that remaining buildings must exceed in order to have an ocean view.

Monotonic stack

We use a stack to keep track of the abovementioned reference heights. As we move from the ocean side inward, each building that has an ocean view is pushed onto the stack. Because the further away from the ocean, the taller the building needs to be to have an ocean view, this stack automatically maintains a monotonic order, where index of the shortest ocean-view building is at the bottom of the stack (pushed earlier during iteration). The index of the tallest (pushed later during iteration) ocean-view building is at the top of the stack.

Python solution

from typing import List


class Solution:
    def findBuildings(self, heights: List[int]) -> List[int]:
        # Initialize monotonic stack to collect index
        stack = []

        # Initialize reference height with -Inf
        max_height = float("-inf")

        # Move from ocean side inward
        for i in reversed(range(len(heights))):
            # Whenever we encounter a building with an ocean view
            #   1. push index to the monotonic stack,
            #   2. update the reference height
            if heights[i] > max_height:
                stack.append(i)
                max_height = heights[i]

        # Because the ocean is on the right,
        #   larger index is at the stack top.
        #   To return index in increasing order,
        #   we reverse the the stack when returning output
        return stack[::-1]

Space and time complexity

With n as the number of buildings in the array heights:

Space complexity: O(n) — The worst-case scenario is that all the buildings have ocean views, so the monotonic stack holds all indexes of the input array
Time complexity: O(n) — We iterate through the input array once

Example unit test (with pytest)

from leetcode_journal.monotonic_stack.buildings_with_an_ocean_view_1762_medium import (
    Solution,
)


def test_no_buildings():
    assert Solution().findBuildings([]) == []


def test_single_buildings():
    assert Solution().findBuildings([1]) == [0]


def test_buildings_of_same_heights():
    assert Solution().findBuildings([1, 1, 1]) == [2]


def test_buildings_of_mixed_heights():
    assert Solution().findBuildings([4, 2, 3, 1]) == [0, 2, 3]