Number of People That Can Be Seen in a Grid

We count people on the right and below independently. We go right-to-left (or bottom-up), and maintain a monotonically decreasing stack.

For the current height, we pop smaller or equal heights from the stack and increase the number of people we can see. If there are remaining elements in the stack, we add one more person to the number of people we can see - unless the last heigth we popped is equal to the current heigth (that person blocks us from seeing a taller one).

Then, we push the current height to the stack.

For the implementation, we can do two passes (for horizontal and vertical directions), or we can do it in one pass if we maintain monostacks for all columns (or rows).

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def monoStack(self, h, ms):
        res = 0
        last = 0
        while ms and ms[-1] <= h:
            last = ms[-1]
            ms.pop()
            res += 1
        res += int(bool(ms) and h != last)
        ms.append(h)
        return res

    def seePeople(self, h: List[List[int]]) -> List[List[int]]:
        m, n = len(h), len(h[0])
        res = [[0] * n for _ in range(m)]
        hms = [[] for _ in range(m)]
        vms = [[] for _ in range(n)]
        
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                res[i][j] = self.monoStack(h[i][j], hms[i]) + self.monoStack(h[i][j], vms[j])

        return res