Abstract / Summary

Find the size of the largest square in a grid that has ones on its border and zeros or ones inside.

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 52% (60k+ submissions).

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 largest1BorderedSquare method receives a binary matrix and returns the area of the biggest square whose four borders are composed entirely of 1s. The algorithm first builds auxiliary tables that store, for each cell, the length of the longest consecutive run of 1s ending at that cell in the horizontal and vertical directions. Using these tables it then scans every possible top-left corner and attempts to enlarge a candidate square, stopping early when the required border lengths are not satisfied. The final result is the square of the side length of the largest valid square found.

Preprocessing Phase

Two matrices, horizontal and vertical, are allocated with the same dimensions as the input grid. Each entry records the count of consecutive 1s that end at the corresponding cell when moving from left to right (horizontal) or from top to bottom (vertical).

horizontal = []
vertical   = []
for y in range(height):
    horizontal.append([0] * width)
    vertical.append([0] * width)
    have = 0
    for x in range(width):
        have += grid[y][x]
        have *= grid[y][x]
        horizontal[y][x] = have

The inner loop accumulates a running total have. When a 0 is encountered, the multiplication by grid[y][x] resets have to 0, effectively breaking the run. The same pattern is applied column-wise to fill vertical:

for x in range(width):
    have = 0
    for y in range(height):
        have += grid[y][x]
        have *= grid[y][x]
        vertical[y][x] = have

These tables enable constant-time checks of border lengths later in the algorithm.

Early Exit Check

Before attempting any square search, the code computes the sum of all values stored in horizontal. Because each entry in horizontal is either 0 or a positive count of consecutive 1s, a total of 0 indicates that the entire grid contains no 1s at all. In that situation the function returns 0 immediately, avoiding unnecessary work.

total = 0
for y in range(height):
    total += sum(horizontal[y])
if total == 0:
    return 0

Main Search Loop

The algorithm iterates over every cell as a potential top-left corner of a square. For each corner it tries side lengths starting just above the current best (result + 1) up to the maximum possible size given the grid dimensions. The candidate bottom-right coordinates (x2, y2) are computed, and three border checks are performed using the precomputed tables:

1. The top border length is verified by ensuring horizontal[y][x2] is at least the candidate side.
2. The left border length is verified by ensuring vertical[y2][x] is at least the candidate side.
3. The bottom and right borders are simultaneously verified by checking horizontal[y2][x2] and vertical[y2][x2].

If any of the first two checks fails, the inner side loop breaks early because larger sides would also fail. When all three checks succeed, result is updated to the larger side length.

largest = min(height, width)
for y in range(height):
    for x in range(width):
        for side in range(result + 1, largest + 1):
            x2 = x + side - 1
            y2 = y + side - 1

            # right border
            if x2 >= width or horizontal[y][x2] < side:
                break
            # bottom border
            if y2 >= height or vertical[y2][x] < side:
                break
            # bottom and right borders together
            if horizontal[y2][x2] >= side and vertical[y2][x2] >= side:
                result = max(result, side)

After all positions have been examined, the function returns the area by squaring the side length stored in result.

return result ** 2

Edge Cases Addressed

The implementation explicitly handles the scenario where the grid contains no 1s, returning 0 without further processing. Boundary conditions are managed by the checks x2 >= width and y2 >= height, which prevent index out-of-range errors when a candidate square would extend beyond the matrix limits. The multiplication step have *= grid[y][x] ensures that any 0 encountered resets the running count, correctly handling isolated 1s and discontinuities in runs.

Performance Optimizations

The most significant optimization is the use of the horizontal and vertical auxiliary tables. By storing the length of consecutive 1s ending at each cell, the algorithm reduces each border verification to a constant-time lookup, eliminating the need to scan the border cells repeatedly. The early-break statements inside the side-expansion loop further prune the search space: as soon as the top or left border fails for a given side length, larger sides are not considered for that top-left corner, saving many unnecessary iterations. The initial total-zero check avoids the entire search when the grid lacks any 1s, providing a fast path for degenerate inputs. These strategies together keep the runtime focused on promising candidates and avoid redundant work.

Imagine looking at a big grid made of little squares, where some are filled with a one and some are filled with a zero. The goal is to find the biggest square shape you can draw that is made only of ones along its edges.

First, the code travels across every row and every column to count how many ones are sitting next to each other in a line. It creates two new maps to keep track of these line counts. This helps know if a line of ones is long enough to form the side of a square.

After that, it looks at every possible spot in the grid to see if a square can start there. It tries making squares of different sizes, starting from small ones and getting bigger. For each size, it checks the four sides. It verifies if the top, bottom, left, and right edges all have enough ones to connect perfectly.

If it finds a square that fits, it remembers how big that side is and keeps looking to see if an even bigger one exists somewhere else. Once it checks all the spots and sizes, the answer represents the area of the biggest square it found.

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#
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#

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