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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Fertile Pyramids in a Land

Difficulty: Hard

Problem Description

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). A pyramidal plot of land can be defined as a set of cells with specific criteria regarding the apex and height, and similarly for an inverse pyramidal plot. Given a binary matrix representing the farmland, return the total number of pyramidal and inverse pyramidal plots that can be found in the grid.

Key Insights

  • Pyramidal and inverse pyramidal plots must consist of more than one cell and all cells must be fertile.
  • Pyramidal plots expand downwards, while inverse pyramidal plots expand upwards from their apex.
  • The size of a plot is determined by the apex position and extends outward based on the height of the pyramid.
  • Efficiently counting plots requires a systematic approach to identify potential apexes and validate the cells forming the plots.

Space and Time Complexity

Time Complexity: O(m * n * min(m, n))
Space Complexity: O(m * n)

Solution

To solve the problem, we will use a dynamic programming approach. We will create two matrices, one for counting potential pyramidal plots and another for inverse pyramidal plots. For each cell in the grid, we will check if it can be the apex of a pyramidal or inverse pyramidal plot by checking the surrounding cells based on the plot's definition. We will sum valid plots while iterating through the grid.

Code Solutions

def countPyramids(grid):
    m, n = len(grid), len(grid[0])
    total_count = 0
    
    # DP arrays to store heights for pyramidal and inverse pyramidal plots
    dp_pyramidal = [[0] * n for _ in range(m)]
    dp_inverse = [[0] * n for _ in range(m)]
    
    # Calculate pyramidal plots
    for r in range(m):
        for c in range(n):
            if grid[r][c] == 1:
                if r == 0:
                    dp_pyramidal[r][c] = 1
                else:
                    # Check if it's a valid apex for a pyramidal plot
                    dp_pyramidal[r][c] = min(dp_pyramidal[r-1][c], dp_pyramidal[r-1][c-1], dp_pyramidal[r-1][c+1] if c+1 < n else 0) + 1
                # Count valid pyramidal plots
                if dp_pyramidal[r][c] > 1:
                    total_count += dp_pyramidal[r][c] - 1

    # Calculate inverse pyramidal plots
    for r in range(m-1, -1, -1):
        for c in range(n):
            if grid[r][c] == 1:
                if r == m-1:
                    dp_inverse[r][c] = 1
                else:
                    # Check if it's a valid apex for an inverse pyramidal plot
                    dp_inverse[r][c] = min(dp_inverse[r+1][c], dp_inverse[r+1][c-1], dp_inverse[r+1][c+1] if c+1 < n else 0) + 1
                # Count valid inverse pyramidal plots
                if dp_inverse[r][c] > 1:
                    total_count += dp_inverse[r][c] - 1

    return total_count
← Back to All Questions