Number of People That Can Be Seen in a Grid - Video Solutions

Problem 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.