# 2282. Number of People That Can Be Seen in a Grid     • Time: $O(mn)$
• Space: $O(mn)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution { public: vector> seePeople(vector>& heights) { const int m = heights.size(); const int n = heights.size(); vector> ans(m, vector(n)); for (int i = 0; i < m; ++i) { stack stack; for (int j = 0; j < n; ++j) { bool hasEqualHeight = false; while (!stack.empty() && heights[i][stack.top()] <= heights[i][j]) { if (heights[i][stack.top()] == heights[i][j]) // edge case: [4, 2, 1, 1, 3] hasEqualHeight = true; ++ans[i][stack.top()], stack.pop(); } if (!stack.empty() && !hasEqualHeight) ++ans[i][stack.top()]; stack.push(j); } } for (int j = 0; j < n; ++j) { stack stack; for (int i = 0; i < m; ++i) { bool hasEqualHeight = false; while (!stack.empty() && heights[stack.top()][j] <= heights[i][j]) { if (heights[stack.top()][j] == heights[i][j]) hasEqualHeight = true; ++ans[stack.top()][j], stack.pop(); } if (!stack.empty() && !hasEqualHeight) ++ans[stack.top()][j]; stack.push(i); } } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class Solution { public int[][] seePeople(int[][] heights) { final int m = heights.length; final int n = heights.length; int[][] ans = new int[m][n]; for (int i = 0; i < m; ++i) { Deque stack = new ArrayDeque<>(); for (int j = 0; j < n; ++j) { boolean hasEqualHeight = false; while (!stack.isEmpty() && heights[i][stack.peek()] <= heights[i][j]) { if (heights[i][stack.peek()] == heights[i][j]) // edge case: [4, 2, 1, 1, 3] hasEqualHeight = true; ++ans[i][stack.pop()]; } if (!stack.isEmpty() && !hasEqualHeight) ++ans[i][stack.peek()]; stack.push(j); } } for (int j = 0; j < n; ++j) { Deque stack = new ArrayDeque<>(); for (int i = 0; i < m; ++i) { boolean hasEqualHeight = false; while (!stack.isEmpty() && heights[stack.peek()][j] <= heights[i][j]) { if (heights[stack.peek()][j] == heights[i][j]) hasEqualHeight = true; ++ans[stack.pop()][j]; } if (!stack.isEmpty() && !hasEqualHeight) ++ans[stack.peek()][j]; stack.push(i); } } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution: def seePeople(self, heights: List[List[int]]) -> List[List[int]]: m = len(heights) n = len(heights) ans = [ * n for _ in range(m)] for i, row in enumerate(heights): stack = [] for j, height in enumerate(row): hasEqualHeight = False while stack and row[stack[-1]] <= height: if row[stack[-1]] == height: # edge case: [4, 2, 1, 1, 3] hasEqualHeight = True ans[i][stack.pop()] += 1 if stack and not hasEqualHeight: ans[i][stack[-1]] += 1 stack.append(j) for j, col in enumerate(zip(*heights)): stack = [] for i, height in enumerate(col): hasEqualHeight = False while stack and col[stack[-1]] <= height: if col[stack[-1]] == height: hasEqualHeight = True ans[stack.pop()][j] += 1 if stack and not hasEqualHeight: ans[stack[-1]][j] += 1 stack.append(i) return ans