LeetCode 2088: Count Fertile Pyramids in a Land Solution
Master LeetCode problem 2088 (Count Fertile Pyramids in a Land), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
2088. Count Fertile Pyramids in a Land
Problem Explanation
Explanation:
To solve this problem, we can iterate through each cell in the grid and consider it as a potential apex for both pyramidal and inverse pyramidal plots. For each apex cell, we can expand in both directions to check if it forms a valid pyramid or inverse pyramid. We can count the number of valid pyramids and inverse pyramids while iterating through the grid.
- For each cell in the grid, we can expand upwards and downwards to check if it forms a valid pyramid and count the number of cells in the pyramid.
- Similarly, we can expand downwards and upwards to check if it forms a valid inverse pyramid and count the number of cells in the inverse pyramid.
- We continue this process for all cells in the grid to find all possible pyramidal and inverse pyramidal plots.
Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the grid. Space Complexity: O(1) - we are not using any extra space proportional to the input.
:
Solution Code
class Solution {
public int countFertilePyramids(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
count += checkPyramids(grid, i, j);
count += checkInversePyramids(grid, i, j);
}
}
return count;
}
private int checkPyramids(int[][] grid, int r, int c) {
int count = 0;
int m = grid.length;
int n = grid[0].length;
for (int h = 1; r + h - 1 < m && c - (h - 1) >= 0 && c + (h - 1) < n; h++) {
boolean validPyramid = true;
for (int i = r; i <= r + h - 1; i++) {
for (int j = c - (i - r); j <= c + (i - r); j++) {
if (grid[i][j] == 0) {
validPyramid = false;
break;
}
}
}
if (validPyramid) {
count++;
} else {
break;
}
}
return count;
}
private int checkInversePyramids(int[][] grid, int r, int c) {
int count = 0;
int m = grid.length;
int n = grid[0].length;
for (int h = 1; r - h + 1 >= 0 && c - (r - 1) >= 0 && c + (r - 1) < n; h++) {
boolean validInversePyramid = true;
for (int i = r; i >= r - h + 1; i--) {
for (int j = c - (r - i); j <= c + (r - i); j++) {
if (grid[i][j] == 0) {
validInversePyramid = false;
break;
}
}
}
if (validInversePyramid) {
count++;
} else {
break;
}
}
return count;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 2088 (Count Fertile Pyramids in a Land)?
This page provides optimized solutions for LeetCode problem 2088 (Count Fertile Pyramids in a Land) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 2088 (Count Fertile Pyramids in a Land)?
The time complexity for LeetCode 2088 (Count Fertile Pyramids in a Land) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 2088 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2088 in Java, C++, or Python.