LeetCode 2282 - Number of People That Can Be Seen in a Grid

Difficulty: 🟡 Medium
Topics: Array, Stack, Matrix, Monotonic Stack

Solution

Problem Understanding

The problem asks us to determine, for each person in a 2D grid of heights, how many other people they can see according to a specific line-of-sight rule. Each person at position (i, j) can see another person either directly to the right in the same row or directly below in the same column. The key restriction is that everyone between the viewer and the target must be shorter than both of them. In other words, the viewer's line-of-sight is blocked by taller or equal-height people in between.

The input is a 2D array heights of size m x n where 1 <= m, n <= 400, and each height value is a positive integer up to 10^5. The output should be an m x n 2D array where each cell contains the number of people the person at that position can see.

Constraints indicate that a brute-force approach scanning every row and column from each person will be potentially very expensive, especially with up to 400 rows and columns, making a naive O(m * n * max(m, n)) approach possibly too slow.

Edge cases include rows or columns with monotonically increasing or decreasing heights, single-row or single-column grids, and grids with identical heights, which may obscure visibility.

Approaches

The brute-force approach would iterate over each person, and for each person, scan to the right along their row and down along their column, counting visible people. For each person, we stop scanning in a direction if a taller or equal-height person is encountered. This approach works because it checks each possible sightline directly, but it is inefficient since each row and column is scanned multiple times.

The optimal approach leverages a monotonic stack to efficiently compute the number of visible people in each row and column. For a given row (or column), we iterate in reverse order (right-to-left for rows, bottom-to-top for columns), using a stack to maintain a decreasing sequence of heights. For each person, we can quickly determine how many people they can see to the right (or below) by counting elements popped from the stack until we encounter a taller or equal-height person. This reduces repeated scanning and lowers the complexity significantly.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m * n * max(m, n))	O(1)	Scan right and down for each person directly, simple but slow
Optimal	O(m * n)	O(max(m, n))	Monotonic stack used per row and per column, much faster

Algorithm Walkthrough

Initialize a 2D array answer of size m x n filled with zeros to store the result.
For each row, use a monotonic stack to compute the number of visible people to the right. Iterate from the last column to the first:

Maintain a stack where each entry stores a height and a count of visible people from that position.
While the current height is greater than the top of the stack, pop the stack and add its count to the current person's count.
If the stack is not empty after popping, increment the count by 1 because the next taller person is visible.
Push the current height and its count onto the stack.

Repeat the same process for each column to compute visible people downward:

Iterate from the last row to the first in the column.
Apply the same monotonic stack logic.

Sum the counts from row-wise and column-wise calculations into answer.
Return the answer array.

Why it works: The monotonic stack maintains the invariant that it contains heights in strictly decreasing order, so popping from the stack effectively counts all consecutively shorter people that are visible until a taller one blocks the line-of-sight. This ensures correct counting without scanning each line repeatedly.

Python Solution

from typing import List

class Solution:
    def seePeople(self, heights: List[List[int]]) -> List[List[int]]:
        m, n = len(heights), len(heights[0])
        answer = [[0] * n for _ in range(m)]
        
        # Count visible people to the right for each row
        for i in range(m):
            stack = []
            for j in range(n - 1, -1, -1):
                count = 0
                while stack and heights[i][j] > stack[-1][0]:
                    count += stack.pop()[1]
                if stack:
                    count += 1
                stack.append((heights[i][j], count))
                answer[i][j] += count
        
        # Count visible people downward for each column
        for j in range(n):
            stack = []
            for i in range(m - 1, -1, -1):
                count = 0
                while stack and heights[i][j] > stack[-1][0]:
                    count += stack.pop()[1]
                if stack:
                    count += 1
                stack.append((heights[i][j], count))
                answer[i][j] += count
        
        return answer

Implementation Walkthrough: First, we initialize the answer grid. Then for each row, we scan from right to left using a stack to count how many people each person can see to their right. The same method is applied for each column scanning from bottom to top to count downward visibility. Stack entries store a height and a count of visible people, which allows us to aggregate counts efficiently. Finally, both counts are summed into answer.

Go Solution

func seePeople(heights [][]int) [][]int {
    m, n := len(heights), len(heights[0])
    answer := make([][]int, m)
    for i := range answer {
        answer[i] = make([]int, n)
    }
    
    // Count visible people to the right
    for i := 0; i < m; i++ {
        stack := [][2]int{}
        for j := n - 1; j >= 0; j-- {
            count := 0
            for len(stack) > 0 && heights[i][j] > stack[len(stack)-1][0] {
                count += stack[len(stack)-1][1]
                stack = stack[:len(stack)-1]
            }
            if len(stack) > 0 {
                count += 1
            }
            stack = append(stack, [2]int{heights[i][j], count})
            answer[i][j] += count
        }
    }
    
    // Count visible people downward
    for j := 0; j < n; j++ {
        stack := [][2]int{}
        for i := m - 1; i >= 0; i-- {
            count := 0
            for len(stack) > 0 && heights[i][j] > stack[len(stack)-1][0] {
                count += stack[len(stack)-1][1]
                stack = stack[:len(stack)-1]
            }
            if len(stack) > 0 {
                count += 1
            }
            stack = append(stack, [2]int{heights[i][j], count})
            answer[i][j] += count
        }
    }
    
    return answer
}

Go-specific Notes: We use slices instead of lists. The stack stores a two-element array [height, count]. The slicing operation stack = stack[:len(stack)-1] is equivalent to pop in Python. We initialize the answer array using make to ensure proper allocation.

Worked Examples

Example 1: heights = [[3,1,4,2,5]]

Processing the row:

Start from right: 5 sees 0
2 sees 1 (5)
4 sees 2 (2 and 5)
1 sees 1 (4)
3 sees 2 (1 and 4)

No downward visibility since it's a single row. Final answer = [[2,1,2,1,0]].

Example 2: heights = [[5,1],[3,1],[4,1]]

Row-wise counts:

Row 0: 5 sees 1, 0; 1 sees 0,0
Row 1: 3 sees 1,0; 1 sees 0,0
Row 2: 4 sees 1,0; 1 sees 0,0

Column-wise counts:

Column 0: 5 sees 2 (3,4); 3 sees 1 (4); 4 sees 0
Column 1: 1 sees 2 (1 below, none taller); 1 sees 1; 1 sees 0

Final answer = [[3,1],[2,1],[1,0]].

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m * n)	Each cell is pushed and popped from the stack at most once per direction, totaling linear in the number of cells
Space	O(max(m, n))	Stack for each row or column, maximum length equals the number of cells in a row or column

The reasoning is that monotonic stack operations are amortized O(1) per element, leading to overall O(m * n) time. Space is dominated by the largest row or column length.

Test Cases

# Provided examples
assert Solution().seePeople([[3,1,4,2,5]])