{x}
blog image

Count Fertile Pyramids in a Land

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.

Solution Explanation

This problem asks us to count the number of pyramidal and inverse pyramidal plots in a given binary matrix. A pyramidal plot is a set of fertile cells (represented by 1s) forming a pyramid shape, with the apex at the top. An inverse pyramidal plot is similar, but with the apex at the bottom.

The solution uses dynamic programming to efficiently count these plots. It iterates through the grid twice: once from bottom to top to count pyramidal plots and once from top to bottom to count inverse pyramidal plots.

Approach

  1. Initialization: A 2D array f of the same size as the input grid is created to store the height of the pyramid at each cell. It's initialized with -1 for barren cells (0s).

  2. Bottom-Up Iteration (Pyramidal Plots): The code iterates through the grid from the bottom row to the top row. For each fertile cell, it checks its three neighbors below (if they exist): the cell directly below and the cells diagonally below and to the left and right. The height of the pyramid at the current cell is the minimum height among these three neighbors, plus 1. This minimum ensures that the pyramid shape is maintained. The height is then added to the total count ans.

  3. Top-Down Iteration (Inverse Pyramidal Plots): The code repeats a similar process, but this time iterating from top to bottom. This counts the inverse pyramids.

  4. Return Value: Finally, the function returns the total count ans, representing the combined number of pyramidal and inverse pyramidal plots.

Code Explanation (Python)

The Python code efficiently implements this approach. Let's break down some key parts:

  • m, n = len(grid), len(grid[0]): Gets the dimensions of the grid.
  • f = [[0] * n for _ in range(m)]: Creates the DP array.
  • The nested loops iterate through the grid. The conditional statements (if grid[i][j] == 0) handle barren cells. The min() function finds the minimum height among the neighbors, ensuring the pyramid shape. ans += f[i][j] adds the height to the total count.

Time and Space Complexity Analysis

  • Time Complexity: O(m*n), where 'm' and 'n' are the dimensions of the input grid. The code iterates through the grid twice.
  • Space Complexity: O(m*n) to store the DP array f.

This dynamic programming approach significantly improves efficiency compared to a brute-force approach, which would have a much higher time complexity. The brute force would have to check all possible pyramid shapes for every cell which would be O(mnk) where k is the maximum height of the pyramid. Our DP solution avoids redundant calculations by storing and reusing previously computed results.