Count Fertile Pyramids in a Land

Hard

Asked by:

10 views

Topics:

ArraysDynamic Programming

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).

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 <= 10⁵
grid[i][j] is either 0 or 1.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the land (number of rows and columns), and what are the upper limits for these dimensions?
Can the values in the land be any other values besides 0 and 1? If not, should I validate this, or is it guaranteed that the land only contains 0s and 1s?
What should I return if the input land is null or empty?
Is there a specific orientation for the pyramids? Are we looking only for pyramids that point upwards or downwards, or both?
Could you define more precisely what constitutes a valid fertile pyramid? Specifically, what is the minimum size of a pyramid (height and base), and is it possible for the base to be equal to only one cell?

Brute Force Solution

Approach

The brute force approach involves checking every possible combination of pyramid shapes that could exist within the land. We'll go through each potential pyramid location and size and then verify if it actually forms a valid pyramid based on the land's fertile plots.

Here's how the algorithm would work step-by-step:

Consider each possible location on the land as the potential tip of a pyramid.
For each potential tip, consider all possible pyramid sizes, starting from a pyramid of size 1.
For each combination of tip location and pyramid size, check if all the locations required to form a pyramid of that size are actually fertile plots in the land.
If all the required locations are fertile, count it as a valid fertile pyramid.
Repeat the above steps for inverted pyramids as well.
After checking all possible tip locations and sizes, the total count of valid fertile pyramids (both normal and inverted) is the final answer.

Code Implementation

def count_fertile_pyramids_brute_force(land):
    rows = len(land)
    cols = len(land[0]) if rows > 0 else 0
    pyramid_count = 0

    def is_valid_pyramid(row_start, col_start, height, inverted):
        for row_offset in range(height):
            width = 2 * row_offset + 1
            col_offset = row_offset
            if col_start - col_offset < 0 or col_start + col_offset >= cols or row_start + row_offset >= rows:
                return False

            for col_index in range(col_start - col_offset, col_start + col_offset + 1):
                actual_row = row_start + row_offset if not inverted else row_start - row_offset
                if actual_row < 0 or actual_row >= rows or land[actual_row][col_index] == 0:
                    return False
        return True

    for row_start in range(rows):
        for col_start in range(cols):
            for height in range(1, min(rows, cols) + 1):
                # Check for normal pyramids
                if row_start + height <= rows:
                    if is_valid_pyramid(row_start, col_start, height, False):
                        pyramid_count += 1

                # Check for inverted pyramids
                if row_start - height + 1 >= 0:
                    # Ensure the entire pyramid remains inside the land.
                    if is_valid_pyramid(row_start, col_start, height, True):
                        pyramid_count += 1
    
    return pyramid_count

Big(O) Analysis

Time Complexity

O(m*n*min(m,n)^3) – Let m be the number of rows and n be the number of columns in the land. We iterate through each cell (m*n) as a potential pyramid tip. For each tip, we consider pyramid sizes up to min(m,n). For each pyramid size, we need to check if all locations within the pyramid are fertile. Checking each pyramid requires visiting a number of cells proportional to the square of the pyramid size, which is at most min(m,n)^2. Thus the time complexity is m*n * min(m,n) * min(m,n)^2 = m*n*min(m,n)^3.

Space Complexity

O(1) – The brute force approach described involves iterating through potential pyramid locations and sizes, but it doesn't explicitly mention the creation of any auxiliary data structures that scale with the input size. The algorithm checks conditions in place to determine pyramid validity. Therefore, the space complexity is dominated by a few integer variables to track locations and sizes, which results in constant auxiliary space.

Optimal Solution

Approach

The key is to build fertile pyramids by efficiently checking for their presence from the bottom up. We'll calculate the number of 'normal' pyramids and 'inverted' pyramids separately, avoiding redundant checks by reusing previously computed information.

Here's how the algorithm would work step-by-step:

First, consider the land as a grid of cells that are either fertile (1) or not (0).
To count normal pyramids, start from the bottom row and move upwards. For each fertile cell, check if it can be the tip of a pyramid.
To determine if a cell can be the tip, verify that the cells directly below it and the cells to either side of those also form a valid layer of the pyramid. Continue this pattern downward.
Keep track of the maximum size pyramid that can be formed with each cell as its tip by building upwards. This helps in later calculations, because we can reuse already calculated pyramid heights.
To count inverted pyramids, follow a similar strategy, but start from the top row and move downwards. This time, you're checking if a fertile cell can be the top of an inverted pyramid.
Again, for each fertile cell, verify that the cells directly above it and to either side form a valid layer. Continue this pattern upwards.
Similarly, track the maximum size inverted pyramid for each cell. This avoids recalculating the same information and makes the process much faster.
Add the counts of normal and inverted pyramids to get the total number of fertile pyramids.

Code Implementation

def count_fertile_pyramids(land):    rows = len(land)
    cols = len(land[0])
    normal_pyramid_counts = [[0] * cols for _ in range(rows)]
    inverted_pyramid_counts = [[0] * cols for _ in range(rows)]
    total_pyramids = 0

    # Iterate to find the number of normal pyramids
    for row in range(rows):
        for col in range(cols):
            if land[row][col] == 1:
                normal_pyramid_counts[row][col] = 1
                if row > 0 and col > 0 and col < cols - 1:
                    normal_pyramid_counts[row][col] += min(normal_pyramid_counts[row - 1][col - 1],
                                                        normal_pyramid_counts[row - 1][col],
                                                        normal_pyramid_counts[row - 1][col + 1])

    # Iterate to find the number of inverted pyramids
    for row in range(rows - 1, -1, -1):
        for col in range(cols):
            if land[row][col] == 1:
                inverted_pyramid_counts[row][col] = 1
                if row < rows - 1 and col > 0 and col < cols - 1:
                    # Reusing already calculated information
                    inverted_pyramid_counts[row][col] += min(inverted_pyramid_counts[row + 1][col - 1],
                                                          inverted_pyramid_counts[row + 1][col],
                                                          inverted_pyramid_counts[row + 1][col + 1])
    for row in range(rows):
        for col in range(cols):
            total_pyramids += normal_pyramid_counts[row][col] + inverted_pyramid_counts[row][col]

    # Subtract the land cells to get only valid pyramids
    total_pyramids -= sum(sum(row) for row in land)
    return total_pyramids

Big(O) Analysis

Time Complexity

O(m * n) – The algorithm iterates through each cell of the m x n land grid to identify potential pyramid tips. For each cell, it extends upwards/downwards to determine the maximum pyramid size possible, potentially examining multiple layers. In the worst-case scenario, for each of the m * n cells, the pyramid height check could iterate through a number of rows proportional to the grid's dimensions. Thus the overall time complexity is O(m * n), where m and n are the dimensions of the land.

Space Complexity

O(M * N) – The algorithm maintains two auxiliary 2D arrays, one for tracking the maximum height of normal pyramids and another for inverted pyramids. Given the land is an M x N grid, both these arrays require M * N space to store height information for each cell. Therefore, the auxiliary space used is proportional to the size of the input grid itself, resulting in a space complexity of O(M * N), where M is the number of rows and N is the number of columns.

Edge Cases

Case	How to Handle
Null or empty input grid	Return 0 immediately as no pyramid can exist in an empty grid.
Grid with only one row or one column	Return 0 since a pyramid requires at least 3 rows and specific width per row.. Check row and column size.
Maximum grid size exceeding memory limitations	Optimize memory usage by processing the grid row by row and releasing memory of previous rows when no longer needed.
Grid filled entirely with 0s (no fertile land)	Return 0 as no pyramid can be constructed with no fertile land.
Grid filled entirely with 1s (completely fertile land)	The algorithm should correctly identify and count all possible pyramids within the all-ones grid.
Integer overflow when calculating pyramid count or dimensions	Use a data type that can accommodate large numbers (e.g., long) or handle intermediate results to prevent overflow.
Input grid with non-binary values (other than 0 or 1)	Treat any value other than 0 as fertile land (equivalent to 1) or explicitly throw an error to indicate invalid input.
Pyramids partially extending beyond grid boundaries	Ensure the pyramid construction logic respects grid boundaries and only counts pyramids that are fully contained within the grid.

Null or empty input grid

How to Handle:

Return 0 immediately as no pyramid can exist in an empty grid.

Grid with only one row or one column

How to Handle:

Return 0 since a pyramid requires at least 3 rows and specific width per row.. Check row and column size.

Maximum grid size exceeding memory limitations

How to Handle:

Optimize memory usage by processing the grid row by row and releasing memory of previous rows when no longer needed.

Grid filled entirely with 0s (no fertile land)

How to Handle:

Return 0 as no pyramid can be constructed with no fertile land.

Grid filled entirely with 1s (completely fertile land)

How to Handle:

The algorithm should correctly identify and count all possible pyramids within the all-ones grid.

Integer overflow when calculating pyramid count or dimensions

How to Handle:

Use a data type that can accommodate large numbers (e.g., long) or handle intermediate results to prevent overflow.

Input grid with non-binary values (other than 0 or 1)

How to Handle:

Treat any value other than 0 as fertile land (equivalent to 1) or explicitly throw an error to indicate invalid input.

Pyramids partially extending beyond grid boundaries

How to Handle:

Ensure the pyramid construction logic respects grid boundaries and only counts pyramids that are fully contained within the grid.