Abstract / Summary

Count how many square pyramids of fertile land exist in a grid using a given threshold value.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 67% (20k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming
• Matrix

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The implementation computes the total number of pyramidal shapes that can be formed on a binary grid where 1 denotes a fertile cell and 0 denotes an infertile one. A pyramid is defined by a contiguous triangle of 1s whose base width grows by two cells for each level down from the apex. Both upright (apex at the top) and inverted (apex at the bottom) pyramids are counted, and only pyramids of height at least two contribute to the final tally.

The algorithm proceeds in three logical phases: building a helper matrix that records consecutive fertile cells to the left of each position, scanning each cell as a potential apex for upright pyramids, and scanning each cell as a potential apex for inverted pyramids. Early termination conditions are embedded in the inner loops to avoid unnecessary work, which yields a practical performance advantage on larger inputs.

Building the left-span matrix

The first nested loop constructs spans, a matrix of the same dimensions as the input grid. Each entry spans[y][x] holds the length of the longest contiguous run of 1s ending at (y, x) when moving leftwards. The code resets the counter to zero whenever a 0 is encountered, ensuring that only fertile cells contribute to the span.

spans = []  # consecutive fertile cells on the left side, including current cell (prefix sum)
for y in range(height):
    row = []
    count = 0
    for x in range(width):
        if grid[y][x] == 0:
            count = 0  # reset
        else:
            count += 1
        row.append(count)
    spans.append(row)

By pre-computing these spans, the later checks for required base widths become constant-time lookups, eliminating the need to scan each row repeatedly.

Counting upright pyramids

The second major block iterates over every cell, treating it as the potential apex of an upright pyramid. For each possible height i (starting at zero), the algorithm computes the coordinates of the cell that would lie on the right edge of the current level: dx = x + i and dy = y + i. If either coordinate exceeds the grid bounds, the inner loop stops. The required base width at level i is need = 2 * i + 1. The pre-computed spans[dy][dx] tells how many consecutive fertile cells exist to the left of (dy, dx). If this span is smaller than need, the pyramid cannot be extended further and the loop breaks. When i reaches at least one, a valid pyramid of height i + 1 has been identified, and the result counter is incremented.

for y in range(height):
    for x in range(width):
        # "normal" pyramids (apex at top)
        for i in range(height):
            dx = x + i
            dy = y + i
            if dx >= width or dy >= height:
                break

            # expected width of pyramid
            need = 2 * i + 1
            if spans[dy][dx] < need:
                break

            # at least two cells high
            if i >= 1:
                result += 1

The loop’s early-exit conditions (dx/dy out of bounds and insufficient span) guarantee that the inner loop runs only as long as a pyramid can possibly exist, preventing wasteful iterations.

Counting inverted pyramids

The third block mirrors the upright logic but walks upward instead of downward. Here dy = y - i moves toward the top of the grid while dx still advances to the right. The same span check applies, and the same height threshold (i >= 1) determines when a pyramid contributes to the count.

# "inverted" pyramids (apex at bottom)
# same code but dy goes up instead of down
for i in range(height):
    dx = x + i
    dy = y - i
    if dx >= width or dy < 0:
        break

    # expected width of pyramid
    need = 2 * i + 1
    if spans[dy][dx] < need:
        break

    # at least two cells high
    if i >= 1:
        result += 1

By reusing the same span matrix, the algorithm avoids recomputing any directional information for the inverted case.

Edge-case handling

The code gracefully manages several boundary situations without additional conditional logic. When the grid contains rows or columns consisting entirely of 0s, the span matrix entries for those cells become zero, causing the inner pyramid loops to break immediately. Single-row or single-column grids are also handled: the outer loops still iterate over every cell, but the inner loops terminate instantly because the calculated dx or dy steps exceed the grid dimensions. Apex cells located on the rightmost column or bottom row cannot form a pyramid of height two, as the required dx or dy would fall outside the grid, triggering the break condition. Similarly, apex cells on the leftmost column cannot start an inverted pyramid because the needed leftward span is never satisfied; the span check fails and the loop exits.

When a pyramid’s base would extend beyond the grid’s right edge, the condition dx >= width stops further growth, ensuring that only fully contained pyramids are counted. For inverted pyramids that would rise above the top row, dy < 0 provides the analogous safeguard.

Performance optimizations

The most significant optimization is the construction of the spans matrix, which transforms a potentially linear scan of each row for every pyramid level into a constant-time verification. This reduces the per-level cost of checking whether a row segment is fully fertile.

The inner loops for both upright and inverted pyramids incorporate two early-exit checks: one for grid boundaries and one for insufficient leftward span. These checks prevent the algorithm from iterating through heights that are impossible given the current apex position, effectively pruning the search space.

By limiting the height iteration to range(height) rather than an unbounded range, the loops respect the maximum possible pyramid height dictated by the grid dimensions. The combination of these bounds and the span-based break condition ensures that the algorithm’s runtime scales with the actual number of feasible pyramids rather than the theoretical maximum.

Overall, the design balances simplicity with targeted pre-processing and early termination, delivering an efficient solution for counting both upright and inverted pyramidal structures in a binary grid.

Imagine a giant grid on the floor made of square tiles. Some tiles have plants growing on them and others are just empty dirt. The goal is to find how many triangle shapes can be built out of the plant tiles.

The first part of the code looks at every single row and counts how many plant tiles are sitting right next to each other. It remembers these numbers so it can easily check if a row is wide enough for a triangle.

Next, the code starts a game of hide and seek to find triangles. It walks through every spot on the grid, acting like it is the top point of a pyramid, and tries to build triangles by going down row by row. It checks if each new row has enough plant tiles to form the wider base of the triangle. If the row is wide enough, the pyramid grows one step bigger. The code does this over and over until it cannot grow the pyramid any further.

After finding all the pyramids pointing up like mountains, the code does the same thing again but points them upside down like the letter V. It checks every spot, acting like the bottom point of a triangle, and grows the shape upwards by checking if there are enough plant tiles in the rows above. Every time a pyramid shape is successfully formed, it adds to the hidden stash of counted triangles.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Python	Java			TS
	WalkCCC	C++		Python	Java
	leetcode.ca	C++		Python	Java		Go
	Progiez	C++		Python	Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007			Python
	suxrobGM					C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality