Largest 1-Bordered Square: Prefix Sum on a Grid

You are given an m x n grid of 0s and 1s. Find the largest square subgrid such that all the cells on its border are 1s, and return its area. The interior can contain anything. If no such square exists, return 0.

This is LeetCode 1139: Largest 1-Bordered Square, and it is a clean example of using precomputed prefix information to answer geometric queries on a matrix. Instead of checking every cell on every candidate border, you precompute two arrays that let you verify an entire border in O(1).

Why this problem matters

The "bordered square" constraint is different from the "all-ones square" in Maximal Square. There, every cell inside the square must be 1. Here, only the border cells matter. That difference changes the approach entirely. The classic min-of-three-neighbors DP does not work because interior cells are irrelevant. Instead, you need a way to quickly check whether a row segment or column segment is entirely ones. That is where consecutive-ones prefix arrays come in.

This problem teaches you to think about borders as four line segments and to precompute information that lets you validate each segment in constant time.

The brute force

The naive approach iterates over every possible square in the grid. For each cell as a potential bottom-right corner, try every possible side length and check every cell on the border. With an m x n grid, there are O(m * n) possible corners, O(min(m, n)) possible side lengths per corner, and O(side) work to verify the border. Total: O(m * n * min(m, n)^2).

You can do much better by precomputing information about consecutive ones.

The approach

Build two prefix arrays:

• hor[r][c]: the number of consecutive 1s ending at (r, c) going left (including the cell itself). If grid[r][c] is 0, then hor[r][c] is 0.
• ver[r][c]: the number of consecutive 1s ending at (r, c) going up (including the cell itself). If grid[r][c] is 0, then ver[r][c] is 0.

Once you have these, checking whether a square of side k with bottom-right corner at (r, c) has an all-ones border becomes four simple comparisons:

1. Bottom row: hor[r][c] must be at least k (k consecutive ones ending at the bottom-right going left).
2. Right column: ver[r][c] must be at least k (k consecutive ones ending at the bottom-right going up).
3. Top row: hor[r - k + 1][c] must be at least k (k consecutive ones ending at the top-right going left).
4. Left column: ver[r][c - k + 1] must be at least k (k consecutive ones ending at the bottom-left going up).

If all four conditions hold, the border is entirely ones. No need to walk through individual cells.

The Python solution

def largest1BorderedSquare(grid):
    m, n = len(grid), len(grid[0])

    hor = [[0] * n for _ in range(m)]
    ver = [[0] * n for _ in range(m)]

    for r in range(m):
        for c in range(n):
            if grid[r][c] == 1:
                hor[r][c] = (hor[r][c - 1] if c > 0 else 0) + 1
                ver[r][c] = (ver[r - 1][c] if r > 0 else 0) + 1

    best = 0

    for r in range(m):
        for c in range(n):
            side = min(hor[r][c], ver[r][c])
            while side > best:
                top_right = hor[r - side + 1][c]
                bottom_left = ver[r][c - side + 1]
                if top_right >= side and bottom_left >= side:
                    best = side
                    break
                side -= 1

    return best * best

The solution has two phases. First, build the prefix arrays in a single pass. Second, for each cell, determine the maximum candidate side from the bottom-right corner and shrink until you find a valid border or exhaust all candidates.

Step-by-step walkthrough

Let's trace the algorithm on a 4x4 grid where the answer is a bordered square of side 4:

1 1 1 1
1 1 1 1
1 1 0 1
1 1 1 1

The 0 at position (2, 2) prevents the interior from being all ones, but that does not matter for a bordered square. All we need is the perimeter to be entirely ones.

At cell (3, 3), both hor[3][3] and ver[3][3] are 4, so we try side 4. The top-right corner (0, 3) has hor[0][3] = 4, and the bottom-left corner (3, 0) has ver[3][0] = 4. All four border checks pass, so the answer is 4 * 4 = 16.

Complexity analysis

Time: O(m * n * min(m, n)). Building the prefix arrays takes O(m * n). For each of the O(m * n) cells, we try at most O(min(m, n)) candidate side lengths. Each candidate check is O(1) thanks to the prefix arrays.

Space: O(m * n). Two prefix arrays, each of size m x n.

The inner while loop might look concerning, but the break on success and the side > best guard mean that in practice the algorithm finishes quickly once it finds a large valid square. The worst case is still O(m * n * min(m, n)), which is fast enough for the constraint of 100 x 100.

The building blocks

This problem is built on two reusable pieces:

1. Consecutive-ones prefix computation

for r in range(m):
    for c in range(n):
        if grid[r][c] == 1:
            hor[r][c] = (hor[r][c - 1] if c > 0 else 0) + 1
            ver[r][c] = (ver[r - 1][c] if r > 0 else 0) + 1

This transforms a binary grid into two tables that answer "how many consecutive ones end here in this direction?" in O(1). The same idea appears in Maximal Rectangle (where you build a vertical histogram of heights per row) and in any problem where you need to validate contiguous runs of values in a matrix.

2. Square border validation

side = min(hor[r][c], ver[r][c])
while side > best:
    if hor[r - side + 1][c] >= side and ver[r][c - side + 1] >= side:
        best = side
        break
    side -= 1

This checks whether a square's four borders are all ones by querying the prefix arrays at the four corners. The bottom row and right column are guaranteed by the initial min, so you only need to verify the top row and left column. This "check the corners" technique applies to any problem where you need to validate rectangular borders on a grid.

Edge cases

• All zeros: every prefix value stays 0. Return 0.
• Single cell [[1]]: hor[0][0] = 1, ver[0][0] = 1. Side 1 is valid. Return 1.
• Single cell [[0]]: return 0.
• All ones: the answer is min(m, n)^2. The entire grid perimeter forms the border of the largest possible square.
• No square larger than 1x1: every 1 cell forms a trivial 1x1 bordered square. The answer is 1 if any cell is 1.
• Single row or single column: the maximum side is 1, so the answer is 1 if any cell is 1, otherwise 0.

From understanding to recall

The idea behind this solution is visual: draw a square on the grid, check its four edges. The prefix arrays make those checks instant. But reproducing it under pressure requires remembering three things: how to build the prefix arrays, how to determine the maximum candidate side at each corner, and how to verify the remaining two borders.

The trickiest detail is getting the indices right. The top-right corner of a square with bottom-right at (r, c) and side k is at (r - k + 1, c). The bottom-left is at (r, c - k + 1). Getting those off by one loses the problem.

Spaced repetition locks in these index calculations. You write the solution from scratch at increasing intervals. After a few reps, the corner formulas become automatic, and you can focus on the bigger-picture strategy instead of fighting with off-by-one errors.

Related posts

• Maximal Square - The classic "all-ones square" DP, where interior cells matter and the min-of-three-neighbors recurrence works
• Maximal Rectangle - Finding the largest all-ones rectangle using histogram stacks, another way to leverage prefix information on a grid
• Range Sum Query 2D - A different flavor of 2D prefix sums, teaching the general technique of precomputing cumulative values on a matrix

CodeBricks breaks problems like this into their reusable building blocks and drills them individually. The consecutive-ones prefix pattern and the border-validation pattern each appear in multiple problems. Drilling them separately with spaced repetition means you recognize and apply them instantly, whether the problem asks about bordered squares, rectangles, or any other shape on a grid.