# Count Fertile Pyramids in a Land
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-fertile-pyramids-in-a-land)
Canonical: https://scaleengineer.com/dsa/problems/count-fertile-pyramids-in-a-land
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Matrix
---
## Problem
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:

1. The number of cells in the set has to be **greater than** `1` and all cells must be **fertile**.
2. 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:

1. The number of cells in the set has to be **greater than** `1` and all cells must be **fertile**.
2. The **apex** of an inverse pyramid is the **bottommost** cell of the inverse pyramid. The **height** of an inverse 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 - h + 1 <= i <= r` **and** `c - (r - i) <= j <= c + (r - i)`.

Some examples of valid and invalid pyramidal (and inverse pyramidal) plots are shown below. Black cells indicate fertile cells.

![](https://assets.glich.co/dsa/count-fertile-pyramids-in-a-land/image0.png) 

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

**Example 1:**

![](https://assets.glich.co/dsa/count-fertile-pyramids-in-a-land/image1.JPG) 

**Input:** grid = [[0,1,1,0],[1,1,1,1]]
**Output:** 2
**Explanation:** The 2 possible pyramidal plots are shown in blue and red respectively.
There are no inverse pyramidal plots in this grid. 
Hence total number of pyramidal and inverse pyramidal plots is 2 + 0 = 2.

**Example 2:**

![](https://assets.glich.co/dsa/count-fertile-pyramids-in-a-land/image2.JPG) 

**Input:** grid = [[1,1,1],[1,1,1]]
**Output:** 2
**Explanation:** The pyramidal plot is shown in blue, and the inverse pyramidal plot is shown in red. 
Hence the total number of plots is 1 + 1 = 2.

**Example 3:**

![](https://assets.glich.co/dsa/count-fertile-pyramids-in-a-land/image3.JPG) 

**Input:** grid = [[1,1,1,1,0],[1,1,1,1,1],[1,1,1,1,1],[0,1,0,0,1]]
**Output:** 13
**Explanation:** There are 7 pyramidal plots, 3 of which are shown in the 2nd and 3rd figures.
There are 6 inverse pyramidal plots, 2 of which are shown in the last figure.
The total number of plots is 7 + 6 = 13.

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 1000`
* `1 <= m * n <= 105`
* `grid[i][j]` is either `0` or `1`.

# Approaches
## Brute Force with Row-wise Prefix Sums
This approach tackles the problem by iterating through every possible cell and treating it as a potential apex for a pyramid. For each potential apex, we attempt to build the largest possible pyramid by expanding downwards, one level at a time. A key optimization is to use row-wise prefix sums to quickly verify if the base of a potential pyramid at each level is composed entirely of fertile cells. This avoids a linear scan of the base at each step. The total number of pyramids is found by summing up the counts for normal pyramids and inverse pyramids, where the latter can be found by applying the same logic to a vertically flipped grid.
**Time:** O(m * n * min(m, n)). We iterate through each of the `m*n` cells as a potential apex. For each apex, we check for heights up to `min(m, n)`. The check for each height is `O(1)` using prefix sums. · **Space:** O(m * n) to store the prefix sum array and the reversed grid.
**Pros:** Conceptually simpler than dynamic programming.; The logic directly follows the definition of a pyramid.
**Cons:** The time complexity is relatively high and may be too slow for the given constraints, although it's an improvement over a naive brute-force solution.; Requires extra space for the prefix sum array and the reversed grid.
### Explanation
The core idea is to check every cell `(r, c)` as a potential apex. If `grid[r][c]` is 1, we check for pyramids of height `h = 2, 3, ...` rooted at this apex. To efficiently check if the base of a pyramid of height `h` is valid (i.e., all cells are fertile), we first precompute a prefix sum array for each row. `prefixSum[i][j]` will store the sum of `grid[i][0]...grid[i][j-1]`. With this, checking if the segment from `j_start` to `j_end` in row `i` is all fertile takes `O(1)` time by checking if `prefixSum[i][j_end+1] - prefixSum[i][j_start]` equals the length of the segment. For each apex `(r, c)`, we find the maximum height `H` and add `H-1` to our total. This process is done for the original grid to count normal pyramids and for a vertically reversed grid to count inverse pyramids.

```java
class Solution {
    public int countPyramids(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int normalPyramids = count(grid, m, n);

        int[][] reversedGrid = new int[m][n];
        for (int i = 0; i < m; i++) {
            reversedGrid[i] = grid[m - 1 - i];
        }

        int inversePyramids = count(reversedGrid, m, n);

        return normalPyramids + inversePyramids;
    }

    private int count(int[][] grid, int m, int n) {
        int[][] prefixSum = new int[m][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefixSum[i][j + 1] = prefixSum[i][j] + grid[i][j];
            }
        }

        int totalPyramids = 0;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 0) {
                    continue;
                }
                int maxHeight = 1;
                for (int h = 2; r + h - 1 < m; h++) {
                    int row = r + h - 1;
                    int startCol = c - (h - 1);
                    int endCol = c + (h - 1);

                    if (startCol < 0 || endCol >= n) {
                        break;
                    }

                    int length = endCol - startCol + 1;
                    if (prefixSum[row][endCol + 1] - prefixSum[row][startCol] == length) {
                        maxHeight = h;
                    } else {
                        break;
                    }
                }
                totalPyramids += maxHeight - 1;
            }
        }
        return totalPyramids;
    }
}
```
### Algorithm
1. The problem can be split into two independent subproblems: counting normal pyramids and counting inverse pyramids. The total count is the sum of the counts from these two subproblems.
2. The logic for counting inverse pyramids is symmetric to counting normal pyramids. We can count normal pyramids on the original grid and then on a vertically flipped version of the grid to get the counts for both types.
3. To count normal pyramids with a brute-force approach, we can iterate through every cell `(r, c)` of the grid.
4. For each cell, if it's fertile (`grid[r][c] == 1`), we consider it a potential apex of a pyramid.
5. We then try to expand downwards, checking for pyramids of increasing height `h = 2, 3, ...`.
6. For a pyramid of height `h` with apex `(r, c)`, the base is at row `r + h - 1` and spans columns from `c - (h - 1)` to `c + (h - 1)`.
7. A naive check of this base would be slow. We can optimize this by pre-calculating row-wise prefix sums. This allows checking if a segment of a row consists entirely of fertile cells in `O(1)` time.
8. For each potential apex `(r, c)`, we find the maximum height `H` it can support. This apex contributes `H - 1` pyramids to the total count (for heights 2 to `H`).
9. The final result is the sum of counts for the original grid (normal pyramids) and the reversed grid (inverse pyramids).

## Dynamic Programming
A more efficient method is to use dynamic programming. The brute-force approach repeatedly checks the same cells, whereas a DP solution can store and reuse these results. We define a DP state `dp[i][j]` to be the height of the largest pyramid with its apex at `(i, j)`. By observing the recursive structure of a pyramid, we can establish a recurrence relation. A pyramid at `(i, j)` is built upon three smaller pyramid structures rooted at `(i+1, j-1)`, `(i+1, j)`, and `(i+1, j+1)`. The height of the pyramid at `(i, j)` is thus limited by the minimum height of these three underlying structures. We can fill the DP table by iterating through the grid. The total count is the sum of `dp[i][j] - 1` for all cells. This process is done for both normal and inverse pyramids (by reversing the grid).
**Time:** O(m * n). We iterate through the grid once to fill the DP table for each type of pyramid. · **Space:** O(m * n) for the DP table. An additional O(m * n) is used for the reversed grid.
**Pros:** Significantly more efficient time complexity than the brute-force approach.; The DP state and transition are logical and build upon the problem's structure.
**Cons:** Requires O(m * n) extra space for the DP table and the reversed grid.
### Explanation
We define a helper function, `count(grid)`, that computes the number of normal pyramids. Inside this function, we create a DP table `dp` of the same size as the grid. We iterate from the bottom row (`i = m-1`) to the top (`i = 0`). For each cell `(i, j)`:
- If `grid[i][j] == 0`, `dp[i][j] = 0`.
- If `grid[i][j] == 1`, we check its neighbors in the row below. If it's a boundary cell (last row, first or last column), the max height is 1. Otherwise, `dp[i][j] = 1 + min(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1])`. The values `dp[i+1]` are already computed due to our bottom-up traversal.
- For each cell, we add `max(0, dp[i][j] - 1)` to our total count.

The main function calls this helper for the original grid and a vertically reversed grid and sums the results.

```java
class Solution {
    public int countPyramids(int[][] grid) {
        return count(grid) + count(reverseGrid(grid));
    }

    private int count(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        int totalPyramids = 0;

        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    dp[i][j] = 0;
                } else {
                    if (i == m - 1 || j == 0 || j == n - 1) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = 1 + Math.min(dp[i + 1][j - 1], 
                                           Math.min(dp[i + 1][j], dp[i + 1][j + 1]));
                    }
                }
                totalPyramids += Math.max(0, dp[i][j] - 1);
            }
        }
        return totalPyramids;
    }

    private int[][] reverseGrid(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] reversed = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                reversed[i][j] = grid[m - 1 - i][j];
            }
        }
        return reversed;
    }
}
```
### Algorithm
1. This approach uses dynamic programming to avoid recomputing information.
2. Let `dp[i][j]` be the height of the largest normal pyramid with its apex at cell `(i, j)`.
3. If `grid[i][j]` is 0, no pyramid can have its apex here, so `dp[i][j] = 0`.
4. If `grid[i][j]` is 1, a pyramid of height `h > 1` can be formed if the cell `(i, j)` sits on top of a valid pyramidal base structure. This structure is itself composed of smaller pyramids.
5. A pyramid of height `h` with apex `(i, j)` exists if `grid[i][j] == 1` and we can form a pyramid of height `h-1` whose base starts at row `i+1` and is centered at column `j`. This is possible if the cells `(i+1, j-1)`, `(i+1, j)`, and `(i+1, j+1)` can support pyramids of sufficient height.
6. This leads to the recurrence relation for normal pyramids: `dp[i][j] = 1 + min(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1])`. This is calculated for `grid[i][j] == 1`.
7. To use this recurrence, we must process the grid from the bottom up (i.e., `i` from `m-1` down to `0`).
8. The number of pyramids with apex `(i, j)` is `dp[i][j] - 1` (since pyramids must have height at least 2).
9. We calculate the total count for normal pyramids, then create a reversed grid and run the same DP logic to count inverse pyramids.

## Space-Optimized Dynamic Programming
This is the most optimal approach, refining the previous DP solution to reduce space complexity. We notice that the DP calculation for any given row only depends on the values from the immediately adjacent row (below for normal pyramids, above for inverse pyramids). Therefore, we can discard the rest of the DP table and only keep track of the previous row's DP values. This reduces the space for the DP table from `O(m*n)` to `O(n)`. Furthermore, to handle inverse pyramids without the `O(m*n)` cost of creating a reversed grid, we implement a second DP pass that iterates through the grid from top to bottom. This results in a highly efficient solution in both time and space.
**Time:** O(m * n). The grid is traversed twice, once for each type of pyramid. · **Space:** O(n), where n is the number of columns. Each DP pass uses two 1D arrays of size n.
**Pros:** Optimal time complexity.; Optimal space complexity, avoiding the need for O(m*n) auxiliary space.
**Cons:** The implementation is slightly more complex due to managing two separate DP passes and row arrays.
### Explanation
The overall structure involves two helper functions, `countNormal` and `countInverse`, both of which use `O(n)` space. The main function sums their results.

`countNormal(grid)`:
- Initializes a `totalCount` to 0 and a `prev_dp` array of size `n`.
- Iterates `i` from `m-1` down to `0`.
- Inside the loop, a `curr_dp` array is created for the current row `i`.
- It's filled using the DP recurrence, referencing `prev_dp` for values from row `i+1`.
- The count is updated with `curr_dp[j] - 1`.
- After row `i` is processed, `prev_dp` is updated to `curr_dp`.

`countInverse(grid)`:
- Follows the same pattern but iterates `i` from `0` to `m-1`.
- The recurrence uses `prev_dp` for values from row `i-1`.

This two-pass approach with `O(n)` space per pass gives the final optimized solution.

```java
class Solution {
    public int countPyramids(int[][] grid) {
        return countNormal(grid) + countInverse(grid);
    }

    private int countNormal(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int totalPyramids = 0;
        int[] prev_dp = new int[n];

        for (int i = m - 1; i >= 0; i--) {
            int[] curr_dp = new int[n];
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    if (i == m - 1 || j == 0 || j == n - 1) {
                        curr_dp[j] = 1;
                    } else {
                        curr_dp[j] = 1 + Math.min(prev_dp[j - 1], Math.min(prev_dp[j], prev_dp[j + 1]));
                    }
                }
                totalPyramids += Math.max(0, curr_dp[j] - 1);
            }
            prev_dp = curr_dp;
        }
        return totalPyramids;
    }

    private int countInverse(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int totalPyramids = 0;
        int[] prev_dp = new int[n];

        for (int i = 0; i < m; i++) {
            int[] curr_dp = new int[n];
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    if (i == 0 || j == 0 || j == n - 1) {
                        curr_dp[j] = 1;
                    } else {
                        curr_dp[j] = 1 + Math.min(prev_dp[j - 1], Math.min(prev_dp[j], prev_dp[j + 1]));
                    }
                }
                totalPyramids += Math.max(0, curr_dp[j] - 1);
            }
            prev_dp = curr_dp;
        }
        return totalPyramids;
    }
}
```
### Algorithm
1. This approach builds upon the `O(m*n)` space DP solution and optimizes its space usage.
2. When calculating the DP values for row `i`, the recurrence only needs the DP values from row `i+1`. This means we don't need to store the entire `m x n` DP table.
3. We can use only two 1D arrays, `prev_dp` (for row `i+1`) and `curr_dp` (for row `i`), each of size `n`.
4. To count normal pyramids, we iterate from `i = m-1` down to `0`. In each iteration, we compute `curr_dp` using `prev_dp`, add the pyramid counts to the total, and then update `prev_dp = curr_dp` for the next iteration.
5. To count inverse pyramids, instead of creating a reversed grid (which costs `O(m*n)` space), we can write a separate function that iterates from top to bottom (`i = 0` to `m-1`). The logic is symmetric, using `prev_dp` for row `i-1` to compute `curr_dp` for row `i`.
6. By having two separate helper functions, one for normal (bottom-up) and one for inverse (top-down) pyramids, we avoid the need for an auxiliary `O(m*n)` grid.

# Solutions
### Java

```java
class Solution {
public
  int countPyramids(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] f = new int[m][n];
    int ans = 0;
    for (int i = m - 1; i >= 0; --i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 0) {
          f[i][j] = -1;
        } else if (i == m - 1 || j == 0 || j == n - 1) {
          f[i][j] = 0;
        } else {
          f[i][j] = Math.min(f[i + 1][j - 1],
                             Math.min(f[i + 1][j], f[i + 1][j + 1])) +
                    1;
          ans += f[i][j];
        }
      }
    }
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 0) {
          f[i][j] = -1;
        } else if (i == 0 || j == 0 || j == n - 1) {
          f[i][j] = 0;
        } else {
          f[i][j] = Math.min(f[i - 1][j - 1],
                             Math.min(f[i - 1][j], f[i - 1][j + 1])) +
                    1;
          ans += f[i][j];
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countPyramids(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    int f[m][n];
    int ans = 0;
    for (int i = m - 1; ~i; --i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 0) {
          f[i][j] = -1;
        } else if (i == m - 1 || j == 0 || j == n - 1) {
          f[i][j] = 0;
        } else {
          f[i][j] = min({f[i + 1][j - 1], f[i + 1][j], f[i + 1][j + 1]}) + 1;
          ans += f[i][j];
        }
      }
    }
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 0) {
          f[i][j] = -1;
        } else if (i == 0 || j == 0 || j == n - 1) {
          f[i][j] = 0;
        } else {
          f[i][j] = min({f[i - 1][j - 1], f[i - 1][j], f[i - 1][j + 1]}) + 1;
          ans += f[i][j];
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countPyramids(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) f = [[0] * n for _ in range(m)] ans = 0 for i in range(m - 1, - 1, - 1): for j in range(n): if grid[i][j] == 0: f[i][j] = - 1 elif not (i == m - 1 or j == 0 or j == n - 1): f[i][j] = min(f[i + 1][j - 1], f[i + 1][j], f[i + 1][j + 1]) + 1 ans += f[i][j] for i in range(m): for j in range(n): if grid[i][j] == 0: f[i][j] = - 1 elif i == 0 or j == 0 or j == n - 1: f[i][j] = 0 else: f[i][j] = min(f[i - 1][j - 1], f[i - 1][j], f[i - 1][j + 1]) + 1 ans += f[i][j] return ans

```