LeetCode 2088 - Count Fertile Pyramids in a Land

The problem gives us a binary matrix where each cell represents a piece of land. A value of 1 means the land is fertile, while 0 means barren. We need to count every valid pyramidal plot and inverse pyramidal plot formed entirely from fertile cells.

leetcodehardarraydynamic-programmingmatrix

LeetCode Problem 2088

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

The problem gives us a binary matrix where each cell represents a piece of land. A value of 1 means the land is fertile, while 0 means barren. We need to count every valid pyramidal plot and inverse pyramidal plot formed entirely from fertile cells.

A normal pyramid points downward. Its apex is the top cell, and every row below expands by one cell on both the left and right sides. For example, a pyramid of height 3 looks like this:

  1
 111
11111

An inverse pyramid points upward. Its apex is the bottom cell, and every row above expands outward similarly.

The important detail is that the height must be greater than 1. A single fertile cell is not considered a pyramid.

The input size is large:

  • m, n <= 1000
  • m * n <= 100000

This tells us that any algorithm worse than roughly O(m * n) or O(m * n * log n) may struggle. A brute-force solution that checks every possible pyramid naively would be too slow.

There are several important edge cases:

  • Grids filled entirely with 0s, where the answer is 0
  • Very small grids like 1 x n or m x 1, where no pyramid can exist because pyramids require expansion
  • Large fully fertile grids, where many overlapping pyramids exist
  • Cells near boundaries, where pyramids cannot expand fully
  • Mixed fertile and barren patterns that break otherwise valid pyramids

The problem guarantees the grid dimensions are valid and every value is either 0 or 1.

Approaches

Brute Force Approach

The brute-force idea is to treat every fertile cell as a possible apex and try to grow a pyramid level by level.

For a normal pyramid:

  1. Start from a cell (r, c)
  2. Try height 2, then 3, and so on
  3. For each height, verify that every required cell exists and is fertile
  4. Stop when any required cell is barren or outside the grid

We repeat the same process for inverse pyramids.

This approach is correct because it explicitly validates every possible pyramid definition from the problem statement. However, it is extremely expensive.

Suppose we have a fully fertile grid. For each cell, we may try many heights, and each height requires scanning an entire row segment. In the worst case, this becomes approximately:

O(m * n * min(m, n)^2)

That is far too slow for 100000 cells.

Optimal Dynamic Programming Approach

The key insight is that a pyramid of height h can only exist if smaller pyramids already exist directly beneath it.

Consider a downward pyramid rooted at (r, c).

For height at least 2:

  • The current cell must be fertile

  • The three supporting positions below must also support pyramids:

  • (r + 1, c - 1)

  • (r + 1, c)

  • (r + 1, c + 1)

This creates a natural dynamic programming relationship.

Instead of checking every cell repeatedly, we compute the maximum pyramid height possible at each position.

If:

dp[r][c] = maximum extra levels below apex

then:

dp[r][c] = 1 + min(
    dp[r + 1][c - 1],
    dp[r + 1][c],
    dp[r + 1][c + 1]
)

for fertile cells.

Every value in dp[r][c] directly contributes that many pyramids:

  • 1 means height 2
  • 2 means heights 2 and 3
  • and so on

We run this DP twice:

  1. Bottom-up for normal pyramids
  2. Top-down for inverse pyramids

This reduces the complexity to linear time.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n * min(m,n)^2) O(1) Explicitly checks every possible pyramid
Optimal Dynamic Programming O(m * n) O(m * n) Computes maximum pyramid height per cell

Algorithm Walkthrough

Step 1: Define the DP Meaning

We create a DP table where:

dp[r][c]

stores how many additional layers can extend from (r, c).

For example:

  • 0 means no pyramid of height greater than 1
  • 1 means a pyramid of height 2
  • 2 means pyramids of heights 2 and 3

This representation lets us directly count valid pyramids.

Step 2: Count Downward Pyramids

We process rows from bottom to top because a pyramid depends on the row beneath it.

For every fertile cell (r, c):

  • If any supporting child position is invalid, the pyramid cannot grow
  • Otherwise:
dp[r][c] =
1 + min(
    dp[r+1][c-1],
    dp[r+1][c],
    dp[r+1][c+1]
)

The minimum matters because the shortest supporting branch limits the total height.

Every computed value contributes directly to the answer.

Step 3: Count Inverse Pyramids

We repeat the same idea in reverse.

Now we process from top to bottom because inverse pyramids depend on rows above.

Transition:

dp[r][c] =
1 + min(
    dp[r-1][c-1],
    dp[r-1][c],
    dp[r-1][c+1]
)

Again, every DP value contributes directly to the total count.

Step 4: Return Total Count

The final answer is:

downward pyramids + inverse pyramids

Why it works

The DP recurrence works because a pyramid of height h exists if and only if all three supporting positions can form pyramids of height at least h - 1.

The minimum supporting height determines the largest possible pyramid centered at the current cell. Since every smaller height is also valid, each DP value directly counts how many pyramids originate from that apex.

This guarantees every valid pyramid is counted exactly once.

Python Solution

from typing import List

class Solution:
    def countPyramids(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        def count_downward() -> int:
            dp = [[0] * cols for _ in range(rows)]
            pyramids = 0

            for r in range(rows - 2, -1, -1):
                for c in range(1, cols - 1):
                    if grid[r][c] == 1:
                        if (
                            grid[r + 1][c - 1] == 1
                            and grid[r + 1][c] == 1
                            and grid[r + 1][c + 1] == 1
                        ):
                            dp[r][c] = 1 + min(
                                dp[r + 1][c - 1],
                                dp[r + 1][c],
                                dp[r + 1][c + 1],
                            )

                            pyramids += dp[r][c]

            return pyramids

        def count_upward() -> int:
            dp = [[0] * cols for _ in range(rows)]
            pyramids = 0

            for r in range(1, rows):
                for c in range(1, cols - 1):
                    if grid[r][c] == 1:
                        if (
                            grid[r - 1][c - 1] == 1
                            and grid[r - 1][c] == 1
                            and grid[r - 1][c + 1] == 1
                        ):
                            dp[r][c] = 1 + min(
                                dp[r - 1][c - 1],
                                dp[r - 1][c],
                                dp[r - 1][c + 1],
                            )

                            pyramids += dp[r][c]

            return pyramids

        return count_downward() + count_upward()

The implementation separates downward and upward pyramid counting into two helper functions. This keeps the logic clean and symmetric.

Each helper allocates a DP table initialized to 0. A value of 0 means no valid pyramid larger than a single cell exists at that position.

For downward pyramids, we iterate upward from the second-last row because every state depends on the row below. We only process interior columns because pyramids cannot expand from edges.

Whenever a fertile cell has all three supporting fertile cells beneath it, we compute its DP value using the minimum of the three supporting DP states.

The same structure is reused for inverse pyramids, except traversal direction changes.

Finally, the two counts are added together.

Go Solution

func countPyramids(grid [][]int) int {
	rows := len(grid)
	cols := len(grid[0])

	countDownward := func() int {
		dp := make([][]int, rows)
		for i := range dp {
			dp[i] = make([]int, cols)
		}

		total := 0

		for r := rows - 2; r >= 0; r-- {
			for c := 1; c < cols-1; c++ {
				if grid[r][c] == 1 &&
					grid[r+1][c-1] == 1 &&
					grid[r+1][c] == 1 &&
					grid[r+1][c+1] == 1 {

					minVal := dp[r+1][c-1]

					if dp[r+1][c] < minVal {
						minVal = dp[r+1][c]
					}

					if dp[r+1][c+1] < minVal {
						minVal = dp[r+1][c+1]
					}

					dp[r][c] = 1 + minVal
					total += dp[r][c]
				}
			}
		}

		return total
	}

	countUpward := func() int {
		dp := make([][]int, rows)
		for i := range dp {
			dp[i] = make([]int, cols)
		}

		total := 0

		for r := 1; r < rows; r++ {
			for c := 1; c < cols-1; c++ {
				if grid[r][c] == 1 &&
					grid[r-1][c-1] == 1 &&
					grid[r-1][c] == 1 &&
					grid[r-1][c+1] == 1 {

					minVal := dp[r-1][c-1]

					if dp[r-1][c] < minVal {
						minVal = dp[r-1][c]
					}

					if dp[r-1][c+1] < minVal {
						minVal = dp[r-1][c+1]
					}

					dp[r][c] = 1 + minVal
					total += dp[r][c]
				}
			}
		}

		return total
	}

	return countDownward() + countUpward()
}

The Go implementation mirrors the Python logic closely. Since Go does not provide a built-in min function for integers, we manually compute the minimum among the three child states.

Slices are used for the DP table, and all values default to zero automatically.

There are no integer overflow concerns because the maximum number of pyramids is bounded by the grid size constraints.

Worked Examples

Example 1

grid = [
  [0,1,1,0],
  [1,1,1,1]
]

Downward DP

We process from bottom to top.

Cell Valid Support? DP Value Total
(0,1) yes 1 1
(0,2) yes 1 2

Both apexes form height-2 pyramids.

Upward DP

There is no row above row 0, so no inverse pyramids exist.

Final answer:

2

Example 2

grid = [
  [1,1,1],
  [1,1,1]
]

Downward DP

Cell DP
(0,1) 1

One downward pyramid exists.

Upward DP

Cell DP
(1,1) 1

One inverse pyramid exists.

Total:

1 + 1 = 2

Example 3

grid = [
  [1,1,1,1,0],
  [1,1,1,1,1],
  [1,1,1,1,1],
  [0,1,0,0,1]
]

Downward DP Construction

Starting from row 2 upward:

Position DP
(1,1) 1
(1,2) 1
(1,3) 1
(0,1) 2
(0,2) 1

Contribution:

1 + 1 + 1 + 2 + 1 = 6

Additional smaller pyramids increase total to 7.

Upward DP Construction

Similarly, upward pyramids contribute 6.

Final answer:

13

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Each cell is processed a constant number of times
Space O(m * n) DP tables store one value per cell

The algorithm performs two passes over the grid, one for downward pyramids and one for inverse pyramids. Each pass examines every cell once and performs only constant-time operations.

The DP tables require storage proportional to the grid size.

Test Cases

from typing import List

class Solution:
    def countPyramids(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        def count_downward() -> int:
            dp = [[0] * cols for _ in range(rows)]
            total = 0

            for r in range(rows - 2, -1, -1):
                for c in range(1, cols - 1):
                    if (
                        grid[r][c] == 1
                        and grid[r + 1][c - 1] == 1
                        and grid[r + 1][c] == 1
                        and grid[r + 1][c + 1] == 1
                    ):
                        dp[r][c] = 1 + min(
                            dp[r + 1][c - 1],
                            dp[r + 1][c],
                            dp[r + 1][c + 1],
                        )
                        total += dp[r][c]

            return total

        def count_upward() -> int:
            dp = [[0] * cols for _ in range(rows)]
            total = 0

            for r in range(1, rows):
                for c in range(1, cols - 1):
                    if (
                        grid[r][c] == 1
                        and grid[r - 1][c - 1] == 1
                        and grid[r - 1][c] == 1
                        and grid[r - 1][c + 1] == 1
                    ):
                        dp[r][c] = 1 + min(
                            dp[r - 1][c - 1],
                            dp[r - 1][c],
                            dp[r - 1][c + 1],
                        )
                        total += dp[r][c]

            return total

        return count_downward() + count_upward()

solution = Solution()

assert solution.countPyramids([[0,1,1,0],[1,1,1,1]]) == 2
# Basic downward pyramids

assert solution.countPyramids([[1,1,1],[1,1,1]]) == 2
# One downward and one upward pyramid

assert solution.countPyramids([
    [1,1,1,1,0],
    [1,1,1,1,1],
    [1,1,1,1,1],
    [0,1,0,0,1]
]) == 13
# Complex overlapping pyramids

assert solution.countPyramids([[0]]) == 0
# Single barren cell

assert solution.countPyramids([[1]]) == 0
# Single fertile cell cannot form pyramid

assert solution.countPyramids([[1,1,1,1]]) == 0
# Single row cannot form pyramid

assert solution.countPyramids([[1],[1],[1]]) == 0
# Single column cannot form pyramid

assert solution.countPyramids([
    [1,1,1],
    [1,0,1],
    [1,1,1]
]) == 0
# Center barren cell blocks all pyramids

assert solution.countPyramids([
    [1,1,1],
    [1,1,1],
    [1,1,1]
]) == 4
# Multiple overlapping pyramids

assert solution.countPyramids([
    [1,1,1,1,1],
    [1,1,1,1,1],
    [1,1,1,1,1]
]) == 8
# Larger dense grid

Test Summary

Test Why
[[0,1,1,0],[1,1,1,1]] Validates simple downward pyramids
[[1,1,1],[1,1,1]] Validates both pyramid directions
Complex 4x5 example Validates overlapping structures
[[0]] Smallest barren input
[[1]] Single fertile cell is invalid
Single row No vertical expansion possible
Single column No horizontal expansion possible
Center zero blocking Ensures interruptions stop pyramids
Full 3x3 grid Validates overlapping counts
Full 3x5 grid Stress test for dense pyramids

Edge Cases

A very important edge case is a grid with only one row or one column. Pyramids require horizontal expansion and multiple rows, so such grids can never contain valid pyramids. A naive implementation might accidentally count single cells as pyramids. This implementation avoids that because the DP transitions only occur when all three supporting cells exist.

Another important case is when fertile regions are interrupted by barren cells. For example, a nearly complete pyramid with a single 0 in the supporting structure should not be counted. The DP transition explicitly checks all three supporting cells before extending a pyramid, so broken structures terminate immediately.

Boundary handling is another common source of bugs. Cells on the leftmost and rightmost columns cannot serve as pyramid centers because expansion would leave the grid. The implementation safely iterates only over columns 1 through cols - 2, preventing out-of-bounds access and invalid pyramid construction.

A final subtle case is overlapping pyramids. A large pyramid contains several smaller pyramids within it. The DP value naturally counts all valid heights simultaneously. For example, if dp[r][c] = 3, that means three distinct pyramids originate from that apex. This ensures no valid structure is missed.