Number of People That Can Be Seen in a Grid

Number of People That Can Be Seen in a Grid

What is this problem about?

The Number of People That Can Be Seen in a Grid problem gives you a matrix of heights. For each cell, count how many other cells can be "seen" — looking right in the same row and looking down in the same column. A person can be seen until a taller-or-equal person blocks the view. This coding problem uses monotonic stacks applied independently to each row and column.

Why is this asked in interviews?

Uber asks this because it requires applying the monotonic stack pattern in two dimensions — once for rows and once for columns. The answer per cell is the sum of visible cells looking right plus visible cells looking down. The array, matrix, monotonic stack, and stack interview pattern is the core technique.

Algorithmic pattern used

Monotonic decreasing stack per row/column. For each row (left to right): process each element using a decreasing stack. For each element popped, it's visible to the current element. If the stack is non-empty after popping, the current element is visible to the stack's top. Count visible pairs. Do the same for each column (top to bottom). Accumulate results.

Example explanation

Grid:

3 1 4 2 5

Processing row with monotonic stack: (3), then 1 (visible to 3, push), then 4 (visible to 1, pop 1; also visible to 3, pop 3; push 4), then 2 (visible to 4, push), then 5 (visible to 2, pop; visible to 4, pop; push 5). Count visible pairs in this row = 5.

Common mistakes candidates make

• Applying a simple scan instead of a monotonic stack (misses non-adjacent visibility).
• Not counting the "seen" element when the stack is non-empty after popping (the new element also sees the remaining top).
• Confusing "left-to-right visibility" with the person looking left.
• Not processing columns independently from rows.

Interview preparation tip

Visibility problems in 1D arrays use monotonic stacks: each element can see elements until a taller one blocks. When processing left-to-right, the stack maintains a decreasing sequence of heights. When a new taller element arrives, it "sees through" all shorter blocked elements before being blocked itself. For grids, apply this independently to each row and each column, then sum. Practice "buildings visible" problems to internalize the monotonic stack visibility pattern.