We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Fertile Pyramids in a Land

Number: 2193

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an m x n binary matrix where 1 represents a fertile cell and 0 represents a barren cell, count the total number of pyramidal plots and inverse pyramidal plots that can be found. A pyramidal plot is defined by an apex (top cell) and extends downwards where each subsequent row increases the horizontal span by one cell at each side compared to the row above. An inverse pyramid is defined similarly but with its apex at the bottom. Note that each valid plot must have more than one cell and every cell within the plot must be fertile.

Key Insights

  • We can solve the problem in two parts: one for pyramidal plots (apex at the top) and one for inverse pyramidal plots (apex at the bottom).
  • Both cases share a similar structure that lends itself to dynamic programming.
  • For pyramids, process the grid bottom-up such that for each cell (i,j) you compute the maximum height of a pyramid with the cell as apex, using the nearby cells (diagonally left, directly below, and diagonally right) from the row below.
  • For inverse pyramids, process the grid top-down similarly.
  • Only pyramids (or inverse pyramids) of height ≥ 2 are valid and count, so subtract 1 from each valid cell’s computed height for counting.
  • The final answer is the sum of counts for both pyramidal and inverse pyramidal plots.

Space and Time Complexity

Time Complexity: O(m * n) – we only traverse each cell a constant number of times. Space Complexity: O(m * n) – we use two auxiliary 2D DP arrays.

Solution

The algorithm uses dynamic programming to compute two matrices:

  1. dpPyramid[i][j]: the maximum height of a valid pyramid with apex at (i, j). Process this from the bottom row upward. For a fertile cell at (i, j), if it is not on the border (which would limit the pyramid’s expansion), its maximum height is determined by taking the minimum of the three possible lower cells (diagonally left, directly below, and diagonally right) and adding one.
  2. dpInv[i][j]: the maximum height of a valid inverse pyramid with apex at (i, j). Process this from the top row downward in a similar manner.

After building these DP tables, for every cell that forms a pyramid (or inverse pyramid) of height at least 2, add (height - 1) to the overall count. This (height - 1) adjustment is because height 1 corresponds to a single cell, which does not count as a valid plot.

Key data structures used:

  • Two 2D arrays (of same dimensions as grid) to store the maximum valid height of a pyramid/inverse pyramid starting at each cell.
  • Iterative loops that calculate the DP values by taking the minimum of three neighbor values in the corresponding direction.

Code Solutions

# Python solution
class Solution:
    def countPyramids(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0

        m, n = len(grid), len(grid[0])
        # dp for pyramidal plots (apex at top)
        dpPyr = [[0] * n for _ in range(m)]
        # dp for inverse pyramidal plots (apex at bottom)
        dpInv = [[0] * n for _ in range(m)]

        total_plots = 0

        # Process pyramids: bottom-up DP
        for i in range(m-1, -1, -1):
            for j in range(n):
                if grid[i][j] == 1:
                    # Bottom row or on the very left/right side: can only form height 1 pyramid
                    if i == m - 1 or j == 0 or j == n - 1:
                        dpPyr[i][j] = 1
                    else:
                        dpPyr[i][j] = min(dpPyr[i+1][j-1], dpPyr[i+1][j], dpPyr[i+1][j+1]) + 1
                    # Only count pyramids with height at least 2
                    if dpPyr[i][j] > 1:
                        total_plots += dpPyr[i][j] - 1

        # Process inverse pyramids: top-down DP
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    # Top row or on the very left/right side: can only form height 1 inverse pyramid
                    if i == 0 or j == 0 or j == n - 1:
                        dpInv[i][j] = 1
                    else:
                        dpInv[i][j] = min(dpInv[i-1][j-1], dpInv[i-1][j], dpInv[i-1][j+1]) + 1
                    # Only count inverse pyramids with height at least 2
                    if dpInv[i][j] > 1:
                        total_plots += dpInv[i][j] - 1

        return total_plots
← Back to All Questions