Count fertile pyramids in a land

Array Dynamic Programming Matrix

66.3% acceptance

Feb 25, 2026

396

A farmer has a rectangular grid of land with m rows and n columns that can be divided into unit cells. Each cell is either fertile (represented by a 1) or barren (represented by a 0). All cells outside the grid are considered barren. A pyramidal plot of land can be defined as a set of cells with the following criteria: The number of cells in the set has to be greater than 1 and all cells must be fertile. The apex of a pyramid is the topmost cell of the pyramid. The height of a pyramid is the number of rows it covers. Let (r, c) be the apex of the pyramid, and its height be h. Then, the plot comprises of cells (i, j) where r <= i <= r + h - 1 and c - (i - r) <= j <= c + (i - r). An inverse pyramidal plot of land can be defined as a set of cells with similar criteria: The number of cells in the set has to be greater than 1 and all cells must be fertile. The apex of an inverse pyramid is the bottommost cell of the inverse pyramid. Let (r, c) be the apex of the pyramid, and its height be h. Then, the plot comprises of cells (i, j) where r - h + 1 <= i <= r and c - (r - i) <= j <= c + (r - i). Given a 0-indexed m x n binary matrix grid representing the farmland, return the total number of pyramidal and inverse pyramidal plots that can be found in grid.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn count_pyramids(grid: Vec<Vec<i32>>) -> i32 {
    let m = grid.len();
    let n = grid[0].len();

    fn count_direction(grid: &Vec<Vec<i32>>, m: usize, n: usize, reverse: bool) -> i32 {
      let mut dp = vec![vec![0i32; n]; m];
      let rows: Vec<usize> = if reverse {
        (0..m).collect()
      } else {
        (0..m).rev().collect()
      };

      // Initialize last/first row
      let base_row = rows[0];
      for j in 0..n {
        dp[base_row][j] = grid[base_row][j];
      }

      let mut count = 0i32;
      for &i in rows.iter().skip(1) {
        let prev = if reverse { i - 1 } else { i + 1 };
        for j in 0..n {
          if grid[i][j] == 0 {
            dp[i][j] = 0;
            continue;
          }
          let mid = dp[prev][j];
          let left = if j > 0 { dp[prev][j - 1] } else { 0 };
          let right = if j + 1 < n { dp[prev][j + 1] } else { 0 };
          dp[i][j] = left.min(mid).min(right) + 1;
          if dp[i][j] > 1 {
            count += dp[i][j] - 1;
          }
        }
      }
      count
    }

    // Count downward pyramids (apex on top) + upward pyramids (apex on bottom)
    count_direction(&grid, m, n, false) + count_direction(&grid, m, n, true)
  }
}