Skip to main content
Talentd

Count Fertile Pyramids in a Land - Solution & Explanation

HardArrayDynamic ProgrammingMatrix18 min readAsked at: Google
Practice this problem

Problem Statement

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.

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:

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:

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:

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.

Approach Overview

Problem Overview: You are given a binary grid where 1 represents fertile land and 0 represents barren land. A pyramid plot is a triangular region of fertile cells expanding downward (or upward for inverse pyramids). The task is to count all valid pyramids of height ≥ 2 that can be formed in the grid.

Approach 1: Dynamic Programming - Bottom-Up for Pyramidal Plot (O(m*n) time, O(m*n) space)

This method detects downward pyramids using dynamic programming over the grid. For each cell, compute the maximum pyramid height with that cell as the apex. A pyramid of height h requires the three cells directly below (left, center, right) to support a pyramid of height h-1. Store the height in a DP matrix while iterating from bottom to top. The number of pyramids contributed by a cell is dp[i][j] - 1. This works because every extra level forms a larger pyramid. The approach scans each cell once and uses local transitions, making it efficient for large matrix inputs.

Approach 2: Dynamic Programming - Top-Down for Inverse Pyramidal Plot (O(m*n) time, O(m*n) space)

Inverse pyramids expand upward instead of downward. The idea mirrors the previous DP but flips the traversal direction. Iterate from top to bottom and compute how large an inverted pyramid can be with the current cell as the bottom apex. The DP state again depends on three supporting cells in the previous row. By maintaining a similar transition formula, you count all inverted pyramids efficiently. Combining counts from both passes ensures every valid pyramid orientation is included. The algorithm relies only on local neighbors and sequential traversal across the array-backed grid.

Recommended for interviews: Interviewers expect the dynamic programming approach with two passes. The key insight is realizing that pyramid height can be derived from the minimum height of three supporting cells. A brute-force approach checking every possible triangle would be O(m*n*min(m,n)) and too slow. Demonstrating the DP transition and counting contribution height - 1 shows strong pattern recognition with matrix DP problems.

Approach 1: Dynamic Programming (Bottom-Up for Pyramidal Plot)

In this approach, we use dynamic programming to determine how many pyramidal plots can be formed with the apex at each cell in the grid. Start by initializing a DP array that indicates the maximum height of a pyramid with its apex at each cell. Traverse the grid row by row, and for each cell that is part of a pyramid, calculate if it can form a part of a larger pyramid by checking the cells directly below and to the sides.

We utilize a 2D DP array to store the maximum possible height of any pyramid at any cell in the grid. The height of a pyramid with apex `(i, j)` is determined by the minimum height of pyramids directly below it, on its left, and on its right, which have their apex at the row below.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n), as we process each cell in the grid once.
Space Complexity: O(m * n), due to the DP array used.

Try this approach in the editor →

Approach 2: Dynamic Programming (Top-Down for Inverse Pyramidal Plot)

This approach is similar to the first but reversed for inverse pyramidal plots. Instead of starting from the top row, we begin from the bottom row, working our way upwards. We use a similar dynamic programming strategy to compute the height of an inverse pyramid, keeping track of all fertile paths.

This solution flips the rows iteration from bottom-to-top for inverse pyramids. It examines if each grid cell can join an inverse pyramid, updating based on fertile status across possible connections.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n).
Space Complexity: O(m * n).

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming (Bottom-Up for Pyramidal Plot)

Time Complexity: O(m * n), as we process each cell in the grid once.
Space Complexity: O(m * n), due to the DP array used.

Dynamic Programming (Top-Down for Inverse Pyramidal Plot)

Time Complexity: O(m * n).
Space Complexity: O(m * n).

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming (Bottom-Up for Pyramidal Plot)O(m*n)O(m*n)Counting downward pyramids efficiently using DP transitions from lower rows
Dynamic Programming (Top-Down for Inverse Pyramidal Plot)O(m*n)O(m*n)Required to count inverted pyramids expanding upward in the grid

Video Solution

Count Fertile Pyramids in a Land | LEETCODE Biweekly Contest 66 | LEETCODE HARD | CODE EXPLAINER • code Explainer • 1,421 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Count Fertile Pyramids in a Land easy or hard?
LeetCode classifies Count Fertile Pyramids in a Land as a Hard problem. The challenge comes from recognizing the pyramid structure and translating it into a dynamic programming relation over the matrix. Once the DP insight is clear, the implementation becomes straightforward.
Count Fertile Pyramids in a Land Python/Java solution
Python and Java implementations typically allocate a DP matrix and iterate through the grid twice. The first pass calculates heights for downward pyramids, and the second pass counts inverted pyramids. Each transition uses the minimum of three neighboring DP values to determine the next height.
How to solve Count Fertile Pyramids in a Land in O(n)?
The problem can be solved in O(m*n) time using dynamic programming on the matrix. Track the largest pyramid height at each cell based on three supporting neighbors. Performing two passes—one for downward pyramids and one for upward pyramids—counts all valid structures efficiently.
What is the best approach for Count Fertile Pyramids in a Land?
Dynamic programming on the grid is the most efficient approach. Compute the maximum pyramid height at every cell using neighbors from the next row (for downward pyramids) and from the previous row (for inverse pyramids). Each cell contributes height-1 pyramids. The total runtime is O(m*n) with O(m*n) space.
Is Count Fertile Pyramids in a Land asked at Google/Amazon/Meta?
Matrix dynamic programming problems similar to Count Fertile Pyramids in a Land appear in interviews at companies like Amazon, Google, and Meta. The problem tests grid traversal, DP state transitions, and pattern recognition in 2D arrays.
What data structure is used in Count Fertile Pyramids in a Land?
The main data structures are a 2D grid (matrix) and a dynamic programming table of the same size. The DP table stores the maximum pyramid height possible with each cell as the apex, enabling constant-time transitions while scanning the matrix.
What is the time complexity of Count Fertile Pyramids in a Land?
The optimal solution runs in O(m*n) time where m is the number of rows and n is the number of columns. Each cell is processed a constant number of times during the downward and upward DP passes. Space complexity is O(m*n) if a separate DP grid is used.

Ready to solve this problem?

Practice Count Fertile Pyramids in a Land with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Square Submatrices with All Ones

Next

Get Biggest Three Rhombus Sums in a Grid