#2088

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Count Fertile Pyramids in a Land

Solve Count Fertile Pyramids in a Land with matrix DP that measures the tallest pyramid rooted at each fertile cell.

Problem Statement

You are given an m by n binary grid where 1 means fertile land and 0 means barren land. A valid pyramid in Count Fertile Pyramids in a Land must be made only of fertile cells, must widen by one cell on both sides at every deeper row, and must stay fully inside the grid because anything outside the grid is effectively barren. Pyramids of height one do not count, so a single fertile cell by itself is not a valid plot.

You need to count both upright pyramids and inverse pyramids. An upright pyramid has its apex on top and expands downward, while an inverse pyramid has its apex on the bottom and expands upward. The main challenge is avoiding repeated width checks for every center and every height, because that becomes too slow on large grids up to 10^5 cells.

Examples

Example 1

Input: grid = [[0,1,1,0],[1,1,1,1]]

Output: 2

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

Input: grid = [[1,1,1],[1,1,1]]

Output: 2

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

Input: grid = [[1,1,1,1,0],[1,1,1,1,1],[1,1,1,1,1],[0,1,0,0,1]]

Output: 13

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.

Solution Approach

Define the DP state by maximum supported height

Let dp[r][c] represent the maximum pyramid height with apex at cell r, c for upright pyramids. If grid[r][c] is 0, the state is 0. If the cell is fertile, its base height starts at 1, and if the row below exists then the pyramid can grow only when the three supporting positions directly below-left, below, and below-right all support enough height. That gives the transition dp[r][c] = 1 + min(dp[r+1][c-1], dp[r+1][c], dp[r+1][c+1]) for interior fertile cells, while edge cells stay at height 1.

Sum only extra layers, not the raw height

Each apex with maximum height h contributes h - 1 valid upright pyramids, because height 2 through height h are all distinct plots and height 1 does not count. This is the key counting detail many solutions miss. Process rows from bottom to top so every transition already knows the best support from the next row, and accumulate max(0, dp[r][c] - 1) into the answer.

Repeat for inverse pyramids with the same pattern

Inverse pyramids are the same state transition dynamic programming pattern with direction flipped. You can either build a second DP from top to bottom, or reverse the grid vertically and reuse the upright routine. This symmetry keeps the implementation clean and avoids separate geometric logic, while still capturing cases like grid = [[1,1,1],[1,1,1]] where one upright and one inverse pyramid both exist.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The optimal DP scans each cell a constant number of times, so the time complexity is O(mn). The straightforward version uses O(mn) extra space for the DP table, though the transition depends on only one adjacent row, so it can be reduced to O(n) space per pass if you manage row buffers carefully.

What Interviewers Usually Probe

They want you to stop brute forcing heights and define a DP state that stores the tallest pyramid centered at each cell.
They are checking whether you notice that every apex contributes multiple pyramids when its maximum height is greater than 2.
They expect you to exploit symmetry for inverse pyramids instead of writing a slow second validation routine.

Common Pitfalls or Variants

Common pitfalls

Counting height 1 cells as pyramids, which inflates the result immediately on dense grids.
Using width validation for every candidate height, which turns this matrix problem into a slow repeated scan.
Forgetting boundary behavior in the transition, especially that edge cells cannot grow because one side of the next row is missing.

Follow-up variants

Return the number of upright pyramids only, which removes the second pass but keeps the same DP transition.
Return the maximum pyramid height anywhere in the grid instead of the total count, which uses the same state without summation.
Allow queries that flip cells between fertile and barren, which breaks the static DP and would need a very different update strategy.

FAQ

What is the core idea behind Count Fertile Pyramids in a Land?

The core idea is state transition dynamic programming on the matrix. For each fertile cell, you compute the tallest pyramid it can be the apex of by looking at three supporting cells in the adjacent row, then add the number of valid heights above one.

Why does the transition use the minimum of three neighboring states?

A pyramid can only grow if its next level is fully supported on the left, center, and right. The smallest of those three heights limits how many complete wider layers can exist below the current apex, so the minimum exactly captures the failure point.

How do you count inverse pyramids in this problem?

Use the same DP idea in the opposite direction. You can scan from top to bottom with a mirrored transition, or reverse the grid vertically and run the upright pyramid routine again.

Why is brute force too slow for problem 2088?

If you try every fertile cell as a center and expand height by height while checking row widths, you repeat work heavily across overlapping pyramids. With up to 10^5 cells, that repeated validation is much slower than one DP pass per orientation.

Can this dynamic programming pattern be optimized for space?

Yes. Each pass depends only on one neighboring row, so you do not need to keep the full m by n table if you only want the count. Rolling arrays can reduce the auxiliary space to O(n), though the indexing becomes easier to get wrong.

terminal

Solution

Solution 1

#### Python3

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

Continue Practicing

#1981 minimize the difference between target and chosen elements #1937 maximum number of points with cost #2267 check if there is a valid parentheses string path