Teaching Kids Programming – Unobstructed Buildings Algorithm via Monotonous Decreasing Stack

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a list of integers heights representing building heights. A building heights[i] can see the ocean if every building on its right has shorter height. Return the building indices where you can see the ocean, in ascending order.

Constraints
0 ≤ n ≤ 100,000 where n is the length of heights
Example 1
Input
heights = [1, 5, 5, 2, 3]
Output
[2, 4]
Explanation
We can see the ocean in building heights[2] and heights[4].

Example 2
Input
heights = [5, 4, 3, 2, 1]
Output
[0, 1, 2, 3, 4]
Explanation
We can see the ocean in every building since each building is taller than every other on its right.

Example 3
Input
heights = [1, 1, 1, 1, 1]
Output
[4]
Explanation
We can’t see the ocean in any building other than the last one.

Bruteforce Algorithm to Compute the Unobstructed Buildings

We can iterate over each building and check if there are any buildings on the right that are same or taller. This takes O(N^2) quadratic time – and O(1) space.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def solve(self, heights):
        ans = []
        if not heights:
            return ans
        n = len(heights)
        for i in range(n):
            anyTall = False
            for j in range(i + 1, n):
                if heights[j] >= heights[i]:
                    anyTall = True
                    break
            if not anyTall:
                ans.append(i)
        return ans

class Solution:
    def solve(self, heights):
        ans = []
        if not heights:
            return ans
        n = len(heights)
        for i in range(n):
            anyTall = False
            for j in range(i + 1, n):
                if heights[j] >= heights[i]:
                    anyTall = True
                    break
            if not anyTall:
                ans.append(i)
        return ans

Keeping Max Right to Compute the Unobstructed Buildings

We can use an array to pre-calculate the maximum height from current to the right. This requires O(N) time and O(N) space. Then, we do another pass to push the indices that are strictly larger than the current max right value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def unobstructedBuildings(self, heights):
        ans = []
        if not heights:
            return ans
        n = len(heights)
        rightMax = [0] * n
        cur = 0
        for i in range(n - 1, -1, -1):
            rightMax[i] = cur
            cur = max(cur, heights[i])
        for i in range(n):
            if heights[i] > rightMax[i]:
                ans.append(i)
        return ans

class Solution:
    def unobstructedBuildings(self, heights):
        ans = []
        if not heights:
            return ans
        n = len(heights)
        rightMax = [0] * n
        cur = 0
        for i in range(n - 1, -1, -1):
            rightMax[i] = cur
            cur = max(cur, heights[i])
        for i in range(n):
            if heights[i] > rightMax[i]:
                ans.append(i)
        return ans

We don’t need to store the all max Right values – instead, we can just dynamically update the max Right value, thus, this takes O(N) time but O(1) space.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def unobstructedBuildings(self, heights):
        max_height_right = float("-inf")
        ans = []
        n = len(heights)
        for i in range(n - 1, -1, -1):
            if heights[i] > max_height_right:
                ans.append(i)
            max_height_right = max(max_height_right, heights[i])
        return ans[::-1]

class Solution:
    def unobstructedBuildings(self, heights):
        max_height_right = float("-inf")
        ans = []
        n = len(heights)
        for i in range(n - 1, -1, -1):
            if heights[i] > max_height_right:
                ans.append(i)
            max_height_right = max(max_height_right, heights[i])
        return ans[::-1]

Using Monotonous Decreasing Stack to Compute the Unobstructed Buildings

We can build a monotonous decreasing stack so that before we push current building, we pop out those previous buildings that are less or equal to current height. THis takes O(N) time and O(N) space.

1
2
3
4
5
6
7
8

class Solution:
    def unobstructedBuildings(self, heights):
        stack = []
        for idx, h in enumerate(heights):
            while stack and heights[stack[-1]] <= h:
                stack.pop()
            stack.append(idx)
        return stack

class Solution:
    def unobstructedBuildings(self, heights):
        stack = []
        for idx, h in enumerate(heights):
            while stack and heights[stack[-1]] <= h:
                stack.pop()
            stack.append(idx)
        return stack

–EOF (The Ultimate Computing & Technology Blog) —