Largest Plus Sign: Dynamic Programming on a Grid

You are given an n x n binary grid where all cells start as 1, except for certain cells that are set to 0 (mines). Your task is to find the order of the largest axis-aligned plus sign made entirely of 1s. A plus sign of order k has a center cell and four arms (up, down, left, right) each of length k - 1, for a total of 4 * (k - 1) + 1 cells. If every cell is a mine, return 0.

This is LeetCode 764: Largest Plus Sign, and it is a clean example of multi-directional DP on a grid.

Why this problem matters

Most grid DP problems involve a single direction of dependency. You fill from top-left to bottom-right, and each cell looks at one or two neighbors. Largest Plus Sign breaks that pattern. Each cell needs information from four directions: how far can you extend up, down, left, and right before hitting a 0 or the grid boundary? The trick is to precompute all four of these independently, then combine them.

This multi-directional DP idea shows up in other problems too. 01 Matrix computes distances in multiple passes. Understanding how to split a problem into directional scans and merge the results is a building block that transfers across grid problems.

The brute force approach

For each cell (r, c) that is a 1, try expanding the plus sign outward. Start with order 1 (just the center). Then check whether all four arms can extend by one more cell. Keep expanding until one arm hits a 0 or a boundary.

The worst case for a single cell is O(n) expansion. You do this for all n^2 cells, giving O(n^3) total. For n = 500, that is 125 million operations, which will be too slow for tight time limits.

The DP insight

Define four tables:

• left[r][c] = number of consecutive 1s from (r, c) going left (including itself)
• right[r][c] = number of consecutive 1s from (r, c) going right
• up[r][c] = number of consecutive 1s from (r, c) going up
• down[r][c] = number of consecutive 1s from (r, c) going down

If grid[r][c] == 0, all four values are 0.

The order of the largest plus sign centered at (r, c) is:

min(left[r][c], right[r][c], up[r][c], down[r][c])

The answer is the maximum of this value across all cells.

Each table can be computed in a single pass. Left goes left to right across each row. Right goes right to left. Up goes top to bottom in each column. Down goes bottom to top. Four O(n^2) passes, plus one final pass to take the min. Total: O(n^2).

def orderOfLargestPlusSign(n, mines):
    grid = [[1] * n for _ in range(n)]
    for r, c in mines:
        grid[r][c] = 0

    left = [[0] * n for _ in range(n)]
    right = [[0] * n for _ in range(n)]
    up = [[0] * n for _ in range(n)]
    down = [[0] * n for _ in range(n)]

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

    for r in range(n):
        for c in range(n - 1, -1, -1):
            if grid[r][c]:
                right[r][c] = (right[r][c + 1] + 1) if c < n - 1 else 1

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

    for c in range(n):
        for r in range(n - 1, -1, -1):
            if grid[r][c]:
                down[r][c] = (down[r + 1][c] + 1) if r < n - 1 else 1

    ans = 0
    for r in range(n):
        for c in range(n):
            ans = max(ans, min(left[r][c], right[r][c], up[r][c], down[r][c]))

    return ans

Walking through an example

Let's trace the algorithm on the 5x5 grid from the diagram above. We compute arm lengths in all four directions, then take the minimum at each cell.

At cell (1, 2), the arm lengths are: left = 2, right = 3, up = 2, down = 2. The minimum is 2, so a plus sign of order 2 can be centered there. Its arms extend one cell in each direction.

At cell (2, 1), the arm lengths are: left = 2, right = 3, up = 3, down = 1. Wait, down is only 1 because of the mine at (3, 1). The minimum would be 1. Let me re-check. Actually, the final grid shows 2 at (2, 1) because left = 2, right = 3, up = 3, down = 1 gives min = 1. But the table shows the value is 2. Let me verify: the mine set is at (3, 1), so down from (2, 1) is just 1 (only itself before hitting the mine below). So the max is at (1, 2) with order 2. The answer is 2.

Complexity analysis

You can optimize space by reusing a single dp table: start every cell at n, then in each directional pass, take the running count and update dp[r][c] = min(dp[r][c], count). This still uses O(n^2) space for the dp table, but avoids allocating four separate tables:

def orderOfLargestPlusSign(n, mines):
    banned = set(map(tuple, mines))
    dp = [[0] * n for _ in range(n)]
    ans = 0

    for r in range(n):
        count = 0
        for c in range(n):
            count = 0 if (r, c) in banned else count + 1
            dp[r][c] = count

        count = 0
        for c in range(n - 1, -1, -1):
            count = 0 if (r, c) in banned else count + 1
            dp[r][c] = min(dp[r][c], count)

    for c in range(n):
        count = 0
        for r in range(n):
            count = 0 if (r, c) in banned else count + 1
            dp[r][c] = min(dp[r][c], count)

        count = 0
        for r in range(n - 1, -1, -1):
            count = 0 if (r, c) in banned else count + 1
            dp[r][c] = min(dp[r][c], count)
            ans = max(ans, dp[r][c])

    return ans

Edge cases to watch for

• All mines: every cell is 0. Return 0.
• No mines: the grid is all 1s. The answer is (n + 1) // 2, since the largest plus sign is limited by the distance from the center to the nearest edge.
• n = 1 with no mines: a single cell of value 1 is a plus sign of order 1.
• Mine at center: the largest plus sign must be found elsewhere. The center cell is not special.
• Mines along one edge: arms in that direction get cut short, but other directions may still allow large plus signs.

The building blocks

Largest Plus Sign is built on one core technique: multi-directional prefix counting. You split the problem into independent directional scans, compute each one in O(n^2), and combine the results with a simple aggregation (min in this case).

The same technique appears in:

• 01 Matrix (LeetCode 542): BFS or two-pass DP to compute distances to the nearest 0. The two-pass approach scans top-left then bottom-right.
• Maximal Square (LeetCode 221): each cell depends on three neighbors (top, left, diagonal). Same grid DP flavor, different recurrence.
• Trapping Rain Water (LeetCode 42): precompute max from left and max from right, then combine.

Once you recognize that a problem requires information from multiple directions, the pattern is always the same: make one pass per direction, store the results, and merge.

From understanding to recall

The algorithm is clean: four passes over the grid, one per direction, counting consecutive 1s. Then one pass to take the min and track the max. The logic is simple to understand. But producing it under pressure means you need to remember to set up four directional scans, get the loop directions right, handle the 0 reset, and combine with min.

Spaced repetition makes this automatic. After a few reps, you see "largest plus sign" and your hands write four directional loops without thinking. The multi-directional DP pattern becomes one of your go-to tools for grid problems.

There are roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems.

Related posts

• Maximal Square - Grid DP where each cell depends on three neighbors, using a similar fill-and-aggregate approach
• 01 Matrix - Multi-directional distance computation on a binary grid using BFS or two-pass DP
• Maximal Rectangle - A harder grid DP problem that reduces rows to histogram stacks