2088. Count Fertile Pyramids in a Land
Problem Description
The problem requires us to find and count all the possible pyramidal and inverse pyramidal plots in a farmer's rectangular grid land, represented by a 2D array grid. Each cell of the grid can either be fertile (value 1) or barren (value 0). A pyramidal plot is a set of fertile cells that form a pyramid shape, with the narrowest point at the top and getting progressively wider until the base. An inverse pyramidal plot, on the other hand, has its narrowest point at the bottom and gets wider towards the top.
A few conditions must be satisfied for the plots:
- For a pyramidal plot, starting with the apex and moving down each row, the width of the plot increases by one cell on both sides. The base will be the widest part of the pyramid.
- For an inverse pyramidal plot, it's the opposite: starting with the apex and moving upwards each row, the width increases by one cell on both sides.
- The number of cells in each plot must be more than one and all must be fertile.
- The apexes of the pyramids must not be on the outer boundary of the grid to ensure there is room for the plot to expand.
The goal of the problem is to determine the total number of valid pyramidal and inverse pyramidal plots that can be found within the given grid.
Intuition
The solution requires a dynamic approach to efficiently count the number of pyramids and inverse pyramids in the grid without having to manually enumerate each possibility which would be computationally expensive.
We can use a dynamic programming array f that mirrors the dimensions of grid to hold the maximum height of a pyramid ending at a given cell (i, j). A cell [i][j] in f represents the maximum height of a pyramid whose apex is at the corresponding cell in grid if the cell is fertile, or -1 if the cell is barren. This approach enables us to build larger pyramids based on smaller ones.
For pyramidal plots, we initialize f to zero and start from the bottom row moving upwards. If a cell is fertile (not on the boundary and grid[i][j] is 1), we check the minimum heights of pyramids that could be formed in the cells below it and to the left and right, and we add 1 to that minimum height to obtain the height of the pyramid for which this cell could be the apex.
For inverse pyramidal plots, we do the opposite. We reset f and start from the top row, moving downwards, updating f in the same manner but based on the cells above each fertile cell.
In both cases, we accumulate the number of plots in a counter ans by adding the heights obtained in f for each fertile cell as we iterate over the grid. This is because for each pyramid with height h, there are h pyramids (nested within one another) ending at that cell.
This way, the final ans will contain the total count of pyramidal and inverse pyramidal plots within the grid.
Learn more about Dynamic Programming patterns.
Which of the following is a min heap? 
Solution Approach
The solution provided uses a dynamic programming approach to efficiently calculate the total number of pyramids and inverse pyramids contained within the grid. Let's break down the key aspects of the implementation:
-
Initialize a matrix
fwith the same dimensions asgrid, to store the number of levels of the largest possible pyramid with its apex at each cell. -
Use two for-loop blocks in the code to iterate over the entire grid twice â once for pyramids and once for inverse pyramids.
-
In the first for-loop block, calculate the number of levels for pyramidal plots:
- Start from the bottom row and move upwards, as pyramids narrow towards the top.
- If the current cell is fertile, set
f[i][j]to the minimum value offat the three cells below and adjacent, plus one (to account for the current cell being a potential apex of a new pyramid level). If it's on the border or barren, setf[i][j]to-1. - Increment
ansby the value off[i][j](except when-1) to count all pyramids ending at that cell.
-
In the second for-loop block, calculate the number of levels for inverse pyramidal plots:
- Start from the top row and move downwards, as inverse pyramids widen towards the top.
- Reset the state of
fbefore starting this block, taking care of the borders where the pyramid cannot be formed. - Follow a similar process as with pyramids, but consider the cells above the current cell and adjacent to it.
- Again, increment
ansby the value off[i][j]for each fertile cell.
-
Return the total count
ansas the sum of pyramid and inverse pyramid counts.
This solution ensures that every possible pyramid, as well as its sub-pyramids resulting from truncating the top levels, is accounted for. Similarly, it takes into account every possible inverse pyramid and its sub-pyramids that can be formed from the bottom up.
The dynamic programming data structure helps bypass the need to examine each potential pyramid individually, which would be prohibitively time-consuming. Instead, by building up from the smallest to the largest pyramid and using the information already computed, we achieve a solution that is much more efficient.
In summary, the provided solution makes use of:
- Dynamic Programming: Storing intermediate results to avoid recalculating them and to build up to the final result.
- Two-pass approach: Performing a pass for standard pyramids and another for inverse pyramids.
- Matrix Manipulation: Iterating through and updating a matrix to track the state of the problem at each step.
- Minimizing function: Using
minto find the smallest pyramid that can be built on the level below, ensuring the pyramid property is sustained.
This approach relies on knowing that the pyramid's property is cumulative; any larger pyramid's base includes several smaller pyramids, which can be immediately inferred from the cell's f value.
In a binary min heap, the minimum element can be found in:
Example Walkthrough
Consider a grid represented by the following 2D array:
1grid = [ 2 [0, 1, 1, 0], 3 [1, 1, 1, 1], 4 [0, 1, 1, 0], 5]
We want to count all possible pyramidal and inverse pyramidal plots within this grid. In this small example, we will walk through the solution approach to illustrate how the count is determined.
Let's first initialize our dynamic programming array f to match the grid dimensions:
1f = [ 2 [-1, 0, 0, -1], 3 [-1, 0, 0, 0,], 4 [-1, 0, 0, -1], 5]
We initialize with 0 for potentially fertile plots (not on the outer boundary initially) and -1 on the outer boundary to avoid considering them as potential apices of pyramids.
Counting Pyramidal Plots
- Starting from the bottom row (row 2) and moving upwards:
- At (2, 1),
f[2][1] = 0(no pyramid possible as it's on the boundary). - At (2, 2),
f[2][2] = 0(same reason as above).
- At (2, 1),
- Next row (row 1):
- At (1, 1),
f[1][1] = min(f[2][1], f[2][2], f[2][1]) + 1 = min(0, 0, 0) + 1 = 1. - At (1, 2),
f[1][2] = min(f[2][2], f[2][1], f[2][2]) + 1 = min(0, 0, 0) + 1 = 1.
- At (1, 1),
Counting the pyramids ending at each cell: ans += f[1][1] + f[1][2] = 1 + 1 = 2.
We stop here since the next row (row 0) has cells on the outer boundary and cannot be the apex of a pyramid.
Counting Inverse Pyramidal Plots
For inverse pyramids, reset f and follow a similar approach but starting from the top of the grid and moving downwards.
- Starting from the top row (row 0) moving downwards:
- At (0, 1),
f[0][1] = 0(no inverse pyramid possible as it's on the boundary). - At (0, 2),
f[0][2] = 0(same reason as above).
- At (0, 1),
- Next row (row 1):
- At (1, 1),
f[1][1] = min(f[0][1], f[0][2], f[0][1]) + 1 = min(0, 0, 0) + 1 = 1. - At (1, 2),
f[1][2] = min(f[0][2], f[0][1], f[0][2]) + 1 = min(0, 0, 0) + 1 = 1.
- At (1, 1),
Increment ans by the value of f[1][1] and f[1][2] for each fertile cell: ans += f[1][1] + f[1][2] = 1 + 1 = 2.
Therefore, the total count of all the pyramidal and inverse pyramidal plots is ans = 2 (pyramidal) + 2 (inverse pyramidal) = 4.
This simple example using a small grid illustrates how the dynamic approach efficiently computes the number of valid pyramidal and inverse pyramidal plots without enumerating each possibility. The approach can be applied to larger grids following the same logic.
Solution Implementation
1from typing import List
2
3class Solution:
4 def countPyramids(self, grid: List[List[int]]) -> int:
5 # Dimensions of the grid.
6 rows, cols = len(grid), len(grid[0])
7
8 # Initialize a matrix to store the heights of the pyramids.
9 pyramid_heights = [[0] * cols for _ in range(rows)]
10
11 # Variable to store the total count of pyramids.
12 total_count = 0
13
14 # Counting the pyramids upside down.
15 for row in range(rows - 1, -1, -1):
16 for col in range(cols):
17 if grid[row][col] == 0:
18 pyramid_heights[row][col] = -1
19 elif row != rows - 1 and col != 0 and col != cols - 1:
20 # get the minimum height of pyramids formed below the current cell
21 # ensuring we can place a pyramid with a valid shape on top
22 pyramid_heights[row][col] = min(
23 pyramid_heights[row + 1][col - 1],
24 pyramid_heights[row + 1][col],
25 pyramid_heights[row + 1][col + 1]
26 ) + 1
27 # Add the count of smaller pyramids contained in the current pyramid.
28 total_count += pyramid_heights[row][col]
29
30 # Flipping the grid to count regular (upright) pyramids by reusing the heights matrix.
31 for row in range(rows):
32 for col in range(cols):
33 if grid[row][col] == 0:
34 pyramid_heights[row][col] = -1
35 elif row == 0 or col == 0 or col == cols - 1:
36 pyramid_heights[row][col] = 0
37 else:
38 # This is similar to the above, but we're moving in the opposite direction.
39 pyramid_heights[row][col] = min(
40 pyramid_heights[row - 1][col - 1],
41 pyramid_heights[row - 1][col],
42 pyramid_heights[row - 1][col + 1]
43 ) + 1
44 total_count += pyramid_heights[row][col]
45
46 return total_count
471class Solution {
2 public int countPyramids(int[][] grid) {
3 int rows = grid.length;
4 int cols = grid[0].length;
5 int[][] pyramidSizes = new int[rows][cols];
6 int pyramidCount = 0;
7
8 // Bottom-up traversal to count all "upside-down" pyramids.
9 for (int row = rows - 1; row >= 0; row--) {
10 for (int col = 0; col < cols; col++) {
11 // If the cell is empty or at the boundary, it cannot form a pyramid.
12 if (grid[row][col] == 0 || row == rows - 1 || col == 0 || col == cols - 1) {
13 pyramidSizes[row][col] = 0;
14 } else {
15 // The size of the pyramid is limited by the size of pyramids in the three cells below.
16 pyramidSizes[row][col] = Math.min(pyramidSizes[row + 1][col - 1],
17 Math.min(pyramidSizes[row + 1][col], pyramidSizes[row + 1][col + 1]))
18 + 1;
19 // Add to the total count of pyramids.
20 pyramidCount += pyramidSizes[row][col];
21 }
22 }
23 }
24
25 // Top-down traversal to count all "right-side-up" pyramids.
26 for (int row = 0; row < rows; row++) {
27 for (int col = 0; col < cols; col++) {
28 // If the cell is empty or at the boundary, it cannot form a pyramid.
29 if (grid[row][col] == 0 || row == 0 || col == 0 || col == cols - 1) {
30 pyramidSizes[row][col] = 0;
31 } else {
32 // The size of the pyramid is limited by the size of pyramids in the three cells above.
33 pyramidSizes[row][col] = Math.min(pyramidSizes[row - 1][col - 1],
34 Math.min(pyramidSizes[row - 1][col], pyramidSizes[row - 1][col + 1]))
35 + 1;
36 // Add to the total count of pyramids,
37 // since this is a separate traversal,
38 // counts both the upside-down and right-side-up pyramids.
39 pyramidCount += pyramidSizes[row][col];
40 }
41 }
42 }
43
44 // Return the total count of both upside-down and right-side-up pyramids.
45 return pyramidCount;
46 }
47}
481#include <vector>
2#include <algorithm> // For min function
3using namespace std;
4
5class Solution {
6public:
7 // Counts the number of pyramids that can be found in the given grid
8 int countPyramids(vector<vector<int>>& grid) {
9 int rowCount = grid.size(); // Number of rows in the grid
10 int colCount = grid[0].size(); // Number of columns in the grid
11 vector<vector<int>> dp(rowCount, vector<int>(colCount, 0)); // Dynamic programming table
12 int totalCount = 0; // Counts total number of pyramids
13
14 // Count pyramids that are pointing upwards
15 for (int i = rowCount - 1; i >= 0; --i) {
16 for (int j = 0; j < colCount; ++j) {
17 if (grid[i][j] == 0) {
18 // If the cell is 0, it canât be part of a pyramid
19 dp[i][j] = -1;
20 } else if (i == rowCount - 1 || j == 0 || j == colCount - 1) {
21 // Border cells can't be the vertex of an upright pyramid
22 dp[i][j] = 0;
23 } else {
24 // Calculate the largest pyramid that can be formed with cell [i,j] as the bottom vertex
25 dp[i][j] = min({dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1]}) + 1;
26 // Add the number of pyramids to totalCount
27 totalCount += dp[i][j];
28 }
29 }
30 }
31
32 // Count pyramids that are pointing downwards
33 for (int i = 0; i < rowCount; ++i) {
34 for (int j = 0; j < colCount; ++j) {
35 if (grid[i][j] == 0) {
36 // If the cell is 0, it canât be part of a pyramid
37 dp[i][j] = -1;
38 } else if (i == 0 || j == 0 || j == colCount - 1) {
39 // Border cells can't be the vertex of an inverted pyramid
40 dp[i][j] = 0;
41 } else {
42 // Calculate the largest pyramid that can be formed with cell [i,j] as the top vertex
43 dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]}) + 1;
44 // Add the number of pyramids to totalCount (without counting the single-cell pyramids again)
45 totalCount += dp[i][j];
46 }
47 }
48 }
49
50 return totalCount; // Return the total number of pyramids in both directions
51 }
52};
531function countPyramids(grid: number[][]): number {
2 const rowCount = grid.length; // Number of rows in the grid
3 const colCount = grid[0].length; // Number of columns in the grid
4 const dp: number[][] = Array.from({ length: rowCount }, () => Array(colCount).fill(0)); // Dynamic programming table
5 let totalCount = 0; // Counts the total number of pyramids
6
7 // Count pyramids pointing upwards
8 for (let i = rowCount - 1; i >= 0; --i) {
9 for (let j = 0; j < colCount; ++j) {
10 if (grid[i][j] === 0) {
11 // If the cell is 0, it canât be part of a pyramid
12 dp[i][j] = -1;
13 } else if (i === rowCount - 1 || j === 0 || j === colCount - 1) {
14 // Border cells can't be the vertex of an upright pyramid
15 dp[i][j] = 0;
16 } else {
17 // Calculate the largest pyramid that can be formed with cell [i, j] as the bottom vertex
18 dp[i][j] = Math.min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1]) + 1;
19 // Add the number of pyramids to totalCount
20 totalCount += dp[i][j];
21 }
22 }
23 }
24
25 // Initialize dp for counting downward-pointing pyramids
26 dp.forEach(row => row.fill(0));
27
28 // Count pyramids pointing downwards
29 for (let i = 0; i < rowCount; ++i) {
30 for (let j = 0; j < colCount; ++j) {
31 if (grid[i][j] === 0) {
32 // If the cell is 0, it canât be part of a pyramid
33 dp[i][j] = -1;
34 } else if (i === 0 || j === 0 || j === colCount - 1) {
35 // Border cells can't be the vertex of an inverted pyramid
36 dp[i][j] = 0;
37 } else {
38 // Calculate the largest pyramid that can be formed with cell [i, j] as the top vertex
39 dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]) + 1;
40 // Add the number of pyramids to totalCount (without counting the single-cell pyramids again)
41 // Subtract 1 to avoid double-counting single-cell pyramids
42 totalCount += (dp[i][j] > 0 ? dp[i][j] - 1 : 0);
43 }
44 }
45 }
46
47 // Return the total count of pyramids in both directions
48 return totalCount;
49}
50Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___ in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
121public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
161function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16Time and Space Complexity
Time Complexity
The given code consists of two main loops that iterate over all cells of the grid. Each cell is processed in constant time, except for a comparison which is also done in constant time.
The outer loops run once for each row in the grid. There are m rows, and for each row, the inner loop runs for each column, of which there are n. Thus, each of these two loops has m * n iterations. Since the outer loops are not nested, the time complexity for both loops combined is O(m * n) + O(m * n), which simplifies to O(m * n).
Therefore, the overall time complexity of the given code is O(m * n).
Space Complexity
The space complexity is determined by the additional space required by the code, not including the input grid. In this case, a 2D list f of the same dimensions as grid is created to store the extents of pyramids buildable at each point, which requires m * n space.
Thus, the space complexity of the code is O(m * n).
Learn more about how to find time and space complexity quickly using problem constraints.
Depth first search can be used to find whether two components in a graph are connected.
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.