Count Fertile Pyramids in a Land — Medium Problem & Solution

A cell of grid is fertile (1) or barren (0). A pyramidal plot of height h > 1 has an apex at (r, c) and covers, for each i from 0 to h-1, every cell in row…

Difficulty: Medium
Topics: Arrays, Dynamic Programming, Matrix
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A cell of grid is fertile (1) or barren (0). A pyramidal plot of height h > 1 has an apex at (r, c) and covers, for each i from 0 to h-1, every cell in row r + i from column c - i to c + i — and every covered cell must be fertile.

An inverse pyramidal plot is the same shape upside down: rows r - i for i from 0 to h-1.

Return the total number of pyramidal and inverse pyramidal plots.

Example 1

Input: grid = [[0,1,1,0],[1,1,1,1]]
Output: 2
Explanation: Two pyramids of height 2, with apexes at (0,1) and (0,2).

Example 2

Input: grid = [[1,1,1],[1,1,1]]
Output: 2
Explanation: One pyramid and one inverse pyramid.

Example 3

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 0
Explanation: No plot of height 2 fits.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 1000
1 <= m * n <= 10^5
grid[i][j] is either 0 or 1.

How to solve Count Fertile Pyramids in a Land

For one orientation, let dp[i][j] be the tallest pyramid whose apex is (i, j). A barren cell gives 0; a cell on the bottom row or on either edge gives 1; otherwise it is one more than the smallest of the three cells directly below. Each cell then contributes dp[i][j] - 1 plots, since heights 2 through dp[i][j] all fit. Run the same pass on the vertically reversed grid for the inverse plots.

Approach

Sweep rows bottom-up. Set dp[i][j] = 0 for barren cells.
Set dp[i][j] = 1 on the last row and on the first and last columns.
Otherwise dp[i][j] = min(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]) + 1.
Accumulate dp[i][j] - 1 over every cell.
Repeat on the row-reversed grid and add the two totals.

Why it works

Taking the minimum of the three cells below is what enforces the widening triangle without checking every cell of it: a pyramid of height h at (i, j) is exactly three overlapping pyramids of height h-1 one row down, and the smallest of them caps how far it can grow. Counting dp - 1 per apex rather than only the tallest is the other half — a tall pyramid contains every shorter one with the same apex, and each is a distinct plot.

Complexity

Time — O(m · n)
Space — O(m · n)

Pitfalls

Height 1 — a single cell — does not count as a plot.
Edge columns can only ever host height 1, since the base would run off the grid.
The inverse plots are a second full pass; they are not double the first.

Reference solution

Python

from typing import List

def countPyramids(grid: List[List[int]]) -> int:
    def one_way(g: List[List[int]]) -> int:
        m, n = len(g), len(g[0])
        dp = [[0] * n for _ in range(m)]
        total = 0
        for i in range(m - 1, -1, -1):
            for j in range(n):
                if g[i][j] == 0:
                    dp[i][j] = 0
                    continue
                if i == m - 1 or j == 0 or j == n - 1:
                    dp[i][j] = 1
                else:
                    dp[i][j] = min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1]) + 1
                total += dp[i][j] - 1
        return total

    return one_way(grid) + one_way(grid[::-1])

JavaScript

var countPyramids = function(grid) {
    var oneWay = function(g) {
        var m = g.length, n = g[0].length, i, j;
        var dp = [];
        for (i = 0; i < m; i++) {
            var row = [];
            for (j = 0; j < n; j++) row.push(0);
            dp.push(row);
        }
        var total = 0;
        for (i = m - 1; i >= 0; i--) {
            for (j = 0; j < n; j++) {
                if (g[i][j] === 0) { dp[i][j] = 0; continue; }
                if (i === m - 1 || j === 0 || j === n - 1) dp[i][j] = 1;
                else dp[i][j] = Math.min(dp[i + 1][j - 1], Math.min(dp[i + 1][j], dp[i + 1][j + 1])) + 1;
                total += dp[i][j] - 1;
            }
        }
        return total;
    };
    var flipped = grid.slice();
    flipped.reverse();
    return oneWay(grid) + oneWay(flipped);
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue