Skip to content

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<vector<int>> seePeople(vector<vector<int>>& heights) {
    const int m = heights.size();
    const int n = heights[0].size();
    vector<vector<int>> ans(m, vector<int>(n));

    for (int i = 0; i < m; ++i) {
      stack<int> 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<int> 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[0].length;
    int[][] ans = new int[m][n];

    for (int i = 0; i < m; ++i) {
      Deque<Integer> 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<Integer> 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[0])
    ans = [[0] * 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