Abstract / Summary

Find the largest square containing only 1s in a 2d grid of 0s and 1s.

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 51% (1+ million 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 solves the classic “maximal square” problem on a binary matrix represented as characters '0' and '1'. It proceeds in two distinct phases. The first phase builds an auxiliary table that records, for each cell, the number of consecutive '1' characters to the right, starting at that cell. The second phase iterates over every cell that can serve as the top-left corner of a square, expanding downward while maintaining the smallest right-run length seen so far. By comparing the current depth with that minimum run length, the algorithm determines the largest square that can be anchored at the current position and updates a global maximum area.

Preprocessing the Right-Run Lengths

The auxiliary structure rightOnes mirrors the dimensions of the input matrix. Each entry rightOnes[y][x] holds the count of consecutive '1' cells beginning at (y, x) and extending to the right edge of the row.

int h = matrix.size();
int w = matrix[0].size();
vector<vector<int>> rightOnes;
rightOnes.resize(h);
for (auto& r : rightOnes)
    r.resize(w);

The nested loops fill the table. When a '0' is encountered the count is zero. If the left neighbor already knows a run length, the current cell can reuse that information by subtracting one, because the run shortens by one position when shifting rightward. Only when the left neighbor does not provide a positive count does the algorithm scan forward to count the run explicitly.

for (int y = 0; y < h; y++)
    for (int x = 0; x < w; x++)
    {
        if (matrix[y][x] == '0')
        {
            rightOnes[y][x] = 0;
            continue;
        }

        if (x > 0 && rightOnes[y][x-1] > 0)
        {
            rightOnes[y][x] = rightOnes[y][x-1] - 1;
            continue;
        }

        int z = 0;
        for (; x+z < w && matrix[y][x+z] == '1'; z++)
            ;
        rightOnes[y][x] = z;
    }

This approach ensures that each row is scanned at most twice: once forward to establish run lengths and once backward via the reuse rule, avoiding redundant character checks.

Scanning for the Maximal Square

After the preprocessing step, the algorithm examines each cell as a potential top-left corner of a square. It skips cells where rightOnes is zero because no square can start there. For a viable cell, it initializes maxRight with the run length at that position and then iterates downward, updating maxRight to the smallest run length encountered in the current column segment. The current depth i+1 and maxRight together bound the side length of any square anchored at the start cell.

int maxx = 0;
for (int y = 0; y < h; y++)
    for (int x = 0; x < w; x++)
    {
        if (rightOnes[y][x] == 0)
            continue;

        int maxRight = rightOnes[y][x];
        for (int i = 0; i+y < h; i++)
        {
            if (maxRight > rightOnes[y+i][x])
                maxRight = rightOnes[y+i][x];

            if (maxRight == 0)
                break;

            int area = i < maxRight ? (i+1)*(i+1) : maxRight*maxRight;
            if (maxx < area)
                maxx = area;

            if (i >= maxRight)
                break;
        }
    }

The inner loop stops early when maxRight becomes zero, indicating that a further extension downward cannot maintain any width of '1'. It also halts when the current depth exceeds maxRight, because the square side cannot be larger than the narrowest horizontal run observed.

The final answer, stored in maxx, represents the area of the largest square of '1's found in the matrix.

Edge Cases Handled

The code gracefully handles matrices that consist entirely of '0' characters. In that scenario every entry of rightOnes becomes zero, the outer scanning loops skip all cells, and the function returns the initial value of maxx, which is zero, correctly indicating that no square of '1' exists.

When the matrix contains a single row or a single column, the preprocessing still computes correct run lengths because the inner forward scan respects the matrix boundaries (x+z < w). The subsequent scanning loop respects the vertical limit (i+y < h), so a one-dimensional matrix yields a maximal square of side length one if any '1' is present, otherwise zero.

If the input matrix is empty or has rows of zero length, the code would attempt to access matrix[0]. However, given the problem constraints that guarantee a non-empty matrix, the implementation assumes valid dimensions and proceeds without additional guards.

Performance Optimizations Observed

The reuse of previously computed right-run lengths via the condition if (x > 0 && rightOnes[y][x-1] > 0) eliminates the need to scan the same row segment repeatedly. This reduces the number of character comparisons dramatically for long stretches of '1'.

The early-exit conditions inside the inner scanning loop (if (maxRight == 0) break; and if (i >= maxRight) break;) prevent unnecessary iterations once it becomes impossible to enlarge the square. By bounding the loop with the smallest horizontal run seen so far, the algorithm avoids exploring deeper rows that cannot contribute to a larger square.

The decision to compute the area using a conditional expression (i < maxRight ? (i+1)*(i+1) : maxRight*maxRight) ensures that the side length used for area calculation never exceeds the limiting dimension, thereby avoiding redundant calculations of impossible square sizes.

Overall, the combination of forward-looking preprocessing, reuse of computed values, and aggressive early termination yields an implementation that scales efficiently with the size of the input matrix while maintaining clear logical structure.

Imagine a large grid made of square tiles. Some tiles are empty and some have a picture of a number one on them. This puzzle asks to find the biggest square made entirely of tiles that have that number one.

First, the code looks at every single spot in the grid. It counts how many tiles with a one are sitting in a row, starting from each spot and moving toward the right side. It saves these counts in a new invisible grid, so it knows exactly how wide a strip of ones is at every position.

Once that is finished, the code looks at every spot again to see if it can be the top-left corner of a big square. It picks a starting point and looks down at the rows below it while using the information from the invisible grid. It checks if the width of the ones in those rows is big enough to hold a square shape. If the width of the ones is at least as wide as the current height of the square being built, then the square is valid. It keeps track of the size of every square found this way and constantly compares them to remember which one is the largest. By the time it finishes checking every possible corner, the biggest square discovered is the answer.

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	C#					Go
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei					Rust
	begeekmyfriend							C
	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai			Java
	chenyanzhe	C++
	everthis						JS
	FelixFan1122				C#
	fengvyi	C++
	fpdjsns	C++
	fsq		Python
	gaosq0604		Python
	gouthampradhan			Java
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	lennylxx	C++
	linouk23	C++
	lkwq007		Python
	MacJim	C++
	qiyuangong		Python
	ruoru					Rust
	sonugiri1043	C++
	suxrobGM				C#
	trung-hn		Python
	varunu28			Java
	vli02							C
	wisdompeak	C++
	yuanliu666								Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
fsq	Python
gaosq0604	Python
gouthampradhan	Java
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C++
linouk23	C++
lkwq007	Python
MacJim	C++
qiyuangong	Python
ruoru	Rust
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
wisdompeak	C++
yuanliu666	Kotlin
zfang399	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