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) —

GD Star Rating
loading...
603 words
Last Post: Teaching Kids Programming - Generate Prime Numbers using Sieve of Eratosthenes Algorithms
Next Post: Filter out Spam Words using PHP Function

The Permanent URL is: Teaching Kids Programming – Unobstructed Buildings Algorithm via Monotonous Decreasing Stack

Leave a Reply