You are given an m x n 0-indexed 2D array of positive integers heights where heights[i][j] is the height of the person standing at position (i, j).
A person standing at position (row1, col1) can see a person standing at position (row2, col2) if:
(row2, col2) is to the right or below the person at (row1, col1). More formally, this means that either row1 == row2 and col1 < col2 or row1 < row2 and col1 == col2.Return an m x n 2D array of integers answer where answer[i][j] is the number of people that the person at position (i, j) can see.
Example 1:
Input: heights = [[3,1,4,2,5]] Output: [[2,1,2,1,0]] Explanation: - The person at (0, 0) can see the people at (0, 1) and (0, 2). Note that he cannot see the person at (0, 4) because the person at (0, 2) is taller than him. - The person at (0, 1) can see the person at (0, 2). - The person at (0, 2) can see the people at (0, 3) and (0, 4). - The person at (0, 3) can see the person at (0, 4). - The person at (0, 4) cannot see anybody.
Example 2:
Input: heights = [[5,1],[3,1],[4,1]] Output: [[3,1],[2,1],[1,0]] Explanation: - The person at (0, 0) can see the people at (0, 1), (1, 0) and (2, 0). - The person at (0, 1) can see the person at (1, 1). - The person at (1, 0) can see the people at (1, 1) and (2, 0). - The person at (1, 1) can see the person at (2, 1). - The person at (2, 0) can see the person at (2, 1). - The person at (2, 1) cannot see anybody.
Constraints:
1 <= heights.length <= 4001 <= heights[i].length <= 4001 <= heights[i][j] <= 105Problem Overview: You are given an m x n grid where each cell represents a person's height. For every position, count how many people they can see looking to the right in the same row and downward in the same column. A person can see shorter people until someone taller or equal appears, and that blocking person is also visible.
Approach 1: Brute Force Visibility Scan (O(m*n*(m+n)) time, O(1) space)
For each cell, scan to the right and downward while tracking the tallest person seen so far. Continue until you encounter a height greater than or equal to the current person's height. Each shorter person that is taller than all previously seen people is visible, and the first blocking person is also counted. This approach is straightforward but inefficient because every cell performs a linear scan across its row and column.
Approach 2: Monotonic Stack (O(m*n) time, O(m*n) space)
The optimal solution processes each row and column using a monotonic stack. Traverse rows from right to left. Maintain a decreasing stack of heights representing candidates that remain visible. While the stack top is shorter than the current height, pop it and increment the visible count. If the stack still contains an element after popping, that taller or equal person is also visible. Push the current height afterward. Repeat the same idea for each column from bottom to top.
This works because the stack maintains a strictly decreasing sequence of heights. Any shorter person hidden behind a taller one is removed immediately, ensuring each element is pushed and popped at most once. The technique is similar to classic visibility problems solved with stacks in arrays and skyline-style problems.
Handling rows and columns independently converts the problem into two linear passes over the matrix. Each pass uses the same stack logic, producing the right-visibility and downward-visibility counts efficiently.
Recommended for interviews: The monotonic stack solution is what interviewers expect. The brute force approach shows you understand the visibility rule, but its O(m*n*(m+n)) runtime does not scale. The stack-based approach reduces the problem to linear passes with O(m*n) time by ensuring each person enters and leaves the stack once.
We observe that for the i-th person, the people he can see must have heights that are strictly monotonically increasing from left to right (or from top to bottom).
Therefore, for each row, we can use a monotonic stack to find the number of people each person can see.
Specifically, we can traverse the array in reverse order, using a stack stk that is monotonically increasing from top to bottom to record the heights of the people we have traversed.
For the i-th person, if the stack is not empty and the top element of the stack is less than heights[i], we increment the number of people the i-th person can see, and then pop the top element of the stack, repeating this until the stack is empty or the top element of the stack is greater than or equal to heights[i]. If the stack is not empty at this point, it means the top element of the stack is greater than or equal to heights[i], so we increment the number of people the i-th person can see by 1. Next, if the stack is not empty and the top element of the stack is equal to heights[i], we pop the top element of the stack. Finally, we push heights[i] onto the stack and continue to the next person.
After processing this way, we can get the number of people each person can see for each row.
Similarly, we can process each column to get the number of people each person can see for each column. Finally, we add the answers for each row and each column to get the final answer.
The time complexity is O(m times n), and the space complexity is O(max(m, n)). Where m and n are the number of rows and columns of the array heights, respectively.
Similar problems:
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Visibility Scan | O(m*n*(m+n)) | O(1) | Good for understanding the visibility rules or very small grids |
| Monotonic Stack (Rows + Columns) | O(m*n) | O(m*n) | Optimal solution for large grids and expected in coding interviews |
Leetcode 2282. Number of People That Can Be Seen in a Grid - monotonic stack: decreasing stack • Code-Yao • 391 views views
Practice Number of People That Can Be Seen in a Grid with our built-in code editor and test cases.
Practice on FleetCode