Count Fertile Pyramids in a Land - Practice Coding Problems

Count Fertile Pyramids in a Land - Problem

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:

The number of cells in the set has to be greater than 1 and all cells must be fertile.
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:

The number of cells in the set has to be greater than 1 and all cells must be fertile.
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).

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.

Input & Output

Example 1 — Basic Grid

$ Input: grid = [[0,1,1,0],[1,1,1,1],[0,1,1,0],[1,1,1,1]]

› Output: 2

💡 Note: Regular pyramid: apex at (1,1) with height 2. Inverse pyramid: apex at (2,1) with height 2. Total = 2 pyramids.

Example 2 — Single Row

$ Input: grid = [[1,1,1]]

› Output: 0

💡 Note: Only one row, so no pyramids with height ≥ 2 can be formed.

Example 3 — All Fertile

$ Input: grid = [[1,1,1],[1,1,1],[1,1,1]]

› Output: 4

💡 Note: Multiple pyramids can be formed: regular pyramids from top row and inverse pyramids from bottom row.

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 1000
1 ≤ m * n ≤ 10⁵
grid[i][j] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Binary matrix with fertile (1) and barren (0) cells

Find Pyramids

Identify valid pyramid shapes (regular and inverse)

Count Total

Sum all pyramids with height ≥ 2

Key Takeaway

🎯 Key Insight: Use dynamic programming to efficiently track maximum pyramid heights at each position, avoiding redundant validations

Asked in

G Google 12 f Facebook 8 a Amazon 6

The key insight is to use dynamic programming to track the maximum pyramid height possible at each position. We build two DP arrays - one for regular pyramids (apex at top) and one for inverse pyramids (apex at bottom). For each fertile cell, we calculate the maximum height by taking the minimum of the three cells below/above it plus 1. Best approach is Dynamic Programming with Time: O(mn), Space: O(mn).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(m²n²)	O(1)	Check every possible pyramid at every position
Dynamic Programming	O(mn)	O(mn)	Build pyramid height arrays incrementally

Brute Force — Algorithm Steps

Step 1: For each cell (r,c), try it as pyramid apex
Step 2: For each height h, check if pyramid of height h is valid
Step 3: Count all valid pyramids and inverse pyramids

Visualization

Tap to expand

Step-by-Step Walkthrough

Choose Apex

Try each cell as pyramid apex

Check Heights

For each height, verify all cells are fertile

Count Valid

Count all valid pyramids found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int isValidPyramid(int** grid, int m, int n, int r, int c, int h, int inverse) {
    for (int i = 0; i < h; i++) {
        int row, left, right;
        if (inverse) {
            row = r - i;
            left = c - i;
            right = c + i;
        } else {
            row = r + i;
            left = c - i;
            right = c + i;
        }
        
        if (row < 0 || row >= m) return 0;
        
        for (int j = left; j <= right; j++) {
            if (j < 0 || j >= n || grid[row][j] == 0) {
                return 0;
            }
        }
    }
    return 1;
}

int solution(int** grid, int gridSize, int* gridColSize) {
    if (gridSize == 0 || gridColSize[0] == 0) return 0;
    
    int m = gridSize, n = gridColSize[0];
    int count = 0;
    
    // Check regular pyramids
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 1) {
                int h = 2;
                while (r + h - 1 < m && isValidPyramid(grid, m, n, r, c, h, 0)) {
                    count++;
                    h++;
                }
            }
        }
    }
    
    // Check inverse pyramids
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 1) {
                int h = 2;
                while (r - h + 1 >= 0 && isValidPyramid(grid, m, n, r, c, h, 1)) {
                    count++;
                    h++;
                }
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Simple parsing for small test cases
    int grid[10][10];
    int* gridPtrs[10];
    int gridColSize[10];
    int gridSize = 0;
    
    // Parse [[0,1,1,0],[1,1,1,1],[0,1,1,0],[1,1,1,1]] format
    char* ptr = line + 1; // Skip first [
    
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            int col = 0;
            while (*ptr && *ptr != ']') {
                if (*ptr >= '0' && *ptr <= '9') {
                    grid[gridSize][col] = *ptr - '0';
                    col++;
                }
                ptr++;
            }
            gridPtrs[gridSize] = grid[gridSize];
            gridColSize[gridSize] = col;
            gridSize++;
        }
        ptr++;
    }
    
    printf("%d\n", solution(gridPtrs, gridSize, gridColSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m²n²)

For each of m*n cells, check pyramids up to min(m,n) height, each requiring O(h²) cell checks

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables for iteration, no extra data structures

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler