Number of people that can be seen in a grid

Array Stack Matrix Monotonic Stack

47.4% acceptance

Mar 31, 2026

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: The person at (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. 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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn see_people(heights: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let m = heights.len();
    let n = heights[0].len();
    let mut answer = vec![vec![0i32; n]; m];
    for i in 0..m {
      let mut stack: Vec<i32> = vec![];
      for j in (0..n).rev() {
        let mut count = 0;
        while !stack.is_empty() && *stack.last().unwrap() < heights[i][j] {
          stack.pop();
          count += 1;
        }
        if !stack.is_empty() {
          count += 1;
        }
        answer[i][j] += count;
        if !stack.is_empty() && *stack.last().unwrap() == heights[i][j] {
          stack.pop();
        }
        stack.push(heights[i][j]);
      }
    }
    for j in 0..n {
      let mut stack: Vec<i32> = vec![];
      for i in (0..m).rev() {
        let mut count = 0;
        while !stack.is_empty() && *stack.last().unwrap() < heights[i][j] {
          stack.pop();
          count += 1;
        }
        if !stack.is_empty() {
          count += 1;
        }
        answer[i][j] += count;
        if !stack.is_empty() && *stack.last().unwrap() == heights[i][j] {
          stack.pop();
        }
        stack.push(heights[i][j]);
      }
    }
    answer
  }
}