Is Number of People That Can Be Seen in a Grid easy or hard?

The problem is rated Medium on LeetCode. The main challenge is recognizing that visibility rules map directly to a monotonic stack pattern rather than naive scanning.

Number of People That Can Be Seen in a Grid Python/Java solution

Implement the monotonic stack technique for each row and column. Use a stack to store candidate heights while iterating in reverse order. The same logic works in Python, Java, C++, Go, and TypeScript with O(m*n) time and linear stack operations.

How to solve Number of People That Can Be Seen in a Grid in O(n)?

Treat each row and column as a visibility problem solved with a monotonic decreasing stack. Process rows from right to left and columns from bottom to top. Pop shorter heights while counting them as visible, then count the first taller or equal blocker if it exists. This ensures linear processing per row or column, resulting in O(m*n) total time.

What is the best approach for Number of People That Can Be Seen in a Grid?

The optimal approach uses a monotonic decreasing stack for each row and each column. Traverse rows from right to left and columns from bottom to top, popping shorter heights while counting visible people. Each element is pushed and popped at most once, giving an overall O(m*n) time complexity.

Is Number of People That Can Be Seen in a Grid asked at Google/Amazon/Meta?

Visibility and monotonic stack problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants such as "Number of Visible People in a Queue" and skyline-style problems test the same stack pattern used in this problem.

What data structure is used in Number of People That Can Be Seen in a Grid?

A monotonic stack is the primary data structure. It maintains a decreasing sequence of heights so hidden shorter people can be removed efficiently while counting visible ones.

What is the time complexity of Number of People That Can Be Seen in a Grid?

The optimal monotonic stack solution runs in O(m*n) time because each cell is processed once in row traversal and once in column traversal. Every height enters and leaves the stack at most once. The brute force alternative takes O(m*n*(m+n)) time due to repeated scans.

Description Hints 4 Solution Video 17:24

2282. Number of People That Can Be Seen in a Grid

Medium46.8% acceptance1 companyPremium elsewhere, free here

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 (row₁, col₁) can see a person standing at position (row₂, col₂) if:

The person at (row₂, col₂) is to the right or below the person at (row₁, col₁). More formally, this means that either row₁ == row₂ and col₁ < col₂ or row₁ < row₂ and col₁ == col₂.
Everyone in between them is shorter than both of them.

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 <= 400
1 <= heights[i].length <= 400
1 <= heights[i][j] <= 10⁵

Asked at 1 company

Uber

Topics

Hints open one at a time

Hint 1

Imagine you are looking to the right. The heights of the people you see form an ascending sequence.

Hint 2

Iterate through the row from right to left. Use a decreasing monotonic stack to keep track of the people that you can see.

Hint 3

Use binary search to find the number of people in the stack that are shorter than the current person.

Hint 4

Repeat this process for each column.

17:24

Still stuck?Read the written solution, or watch a walkthrough.

Open solution