Count Fertile Pyramids in a Land

Count Fertile Pyramids in a Land

What is this problem about?

The Count Fertile Pyramids in a Land coding problem involves a 2D grid representing land where 1 is fertile and 0 is barren. You need to count all "fertile pyramids" and "inverse fertile pyramids." A pyramid of height h has a base of 2h-1 fertile cells and tapers up to a single fertile cell at the apex.

Why is this asked in interviews?

Google asks the Matrix interview pattern for this problem to test your ability to use Dynamic Programming in 2D grids. It’s a "Hard" difficulty problem because counting every possible pyramid manually is too slow. It evaluates whether you can define a DP state where dp[r][c] represents the maximum height of a pyramid centered at that cell.

Algorithmic pattern used

The problem uses 2D Dynamic Programming.

1. Define dp[r][c] as the height of the largest pyramid whose apex is at (r, c).
2. For a pyramid: dp[r][c] = 1 + min(dp[r+1][c-1], dp[r+1][c], dp[r+1][c+1]).
3. Calculate this for both standard pyramids (looking down) and inverse pyramids (looking up).
4. The number of pyramids for a cell with dp[r][c] = h is h - 1 (since a height-1 cell is just a cell, not a pyramid).
5. Sum up (dp[r][c] - 1) for all cells in both passes.

Example explanation

Grid: 0 1 0 1 1 1

1. The bottom row has no pyramids below it.
2. Cell (0, 1) has 1, 1, 1 below it.
3. dp[0][1] = 1 + min(dp[1][0], dp[1][1], dp[1][2]) = 1 + 1 = 2.
4. Pyramid count for this cell = 2 - 1 = 1. Result: 1.

Common mistakes candidates make

• Iterating from Wrong Direction: Forgetting that the DP for a standard pyramid must be calculated bottom-up, while the inverse pyramid must be top-down.
• Off-by-one in base: Not realizing that a pyramid of height h needs a specific horizontal spread at each level.
• Initialization: Not correctly handling the edges of the grid where a pyramid cannot be centered.

Interview preparation tip

This problem is very similar to "Count Square Submatrices." If you can solve the square problem, you can solve the pyramid problem by adjusting the min() condition to look at three neighbors instead of two.