LeetCode 764 - Largest Plus Sign

This problem asks us to find the largest axis-aligned plus sign made entirely of 1s in an n x n binary grid. Initially, every cell in the grid contains 1. However, some positions are marked as mines, meaning those cells contain 0.

leetcodemediumarraydynamic-programming

LeetCode Problem 764

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

This problem asks us to find the largest axis-aligned plus sign made entirely of 1s in an n x n binary grid.

Initially, every cell in the grid contains 1. However, some positions are marked as mines, meaning those cells contain 0. The input mines provides the coordinates of all such blocked cells.

A plus sign of order k consists of:

  • A center cell containing 1
  • Four arms extending in the up, down, left, and right directions
  • Each arm must have length k - 1
  • Every cell involved must contain 1

For example, a plus sign of order 3 means:

  • One center cell
  • Two continuous 1s in every direction

Visually:

    1
    1
1 1 1 1 1
    1
    1

The goal is to return the largest possible order of any valid plus sign in the grid. If no valid plus sign exists, return 0.

The phrase axis-aligned means the plus sign can only extend vertically and horizontally, not diagonally.

Understanding the Input

The input consists of:

  • n: the dimension of the square grid (n x n)
  • mines: a list of coordinates where the grid contains 0

For example:

n = 5
mines = [[4,2]]

This means:

  • Create a 5 x 5 grid filled with 1s
  • Set grid[4][2] = 0

Everything else remains 1.

Understanding the Output

The output is a single integer representing the largest order of any plus sign.

Suppose the maximum plus sign has:

  • center = (2,2)
  • arm length = 1

Then:

order = arm length + 1 = 2

So the answer would be 2.

What the Constraints Tell Us

The constraints are:

1 <= n <= 500
1 <= mines.length <= 5000

The largest possible grid contains:

500 × 500 = 250,000 cells

This is too large for expensive repeated scanning around every cell.

A naive solution that repeatedly expands outward from every candidate center could easily become too slow, especially if each expansion costs O(n) and is repeated for all O(n²) cells.

This strongly suggests we need an efficient dynamic programming style preprocessing solution, ideally around O(n²) time.

Important Edge Cases

Several edge cases can easily break naive implementations.

If the entire grid is mined, no plus sign exists. For example:

n = 1
mines = [[0,0]]

The answer must be 0.

If there are no mines in a small grid:

n = 1
mines = []

The only cell itself forms a plus sign of order 1.

Another tricky case occurs when a center looks promising but one direction is blocked early:

1 1 1
1 1 0
1 1 1

The center cannot extend fully in all four directions, so the order becomes limited by the shortest arm.

The key observation is that the order of a plus sign is determined by the minimum arm length among all four directions.

Approaches

Brute Force Approach

The brute force idea is to treat every cell as a possible center of a plus sign.

For each candidate cell:

  1. Check whether it contains 1
  2. Expand outward level by level
  3. Verify all four directions at the same distance
  4. Stop when one direction hits a boundary or mine
  5. Record the largest valid order

For example, if checking center (r,c):

distance = 1:
up, down, left, right must all be 1

distance = 2:
same requirement

The order becomes the maximum successful expansion plus one.

This approach is correct because it explicitly validates every possible plus sign. However, it is inefficient.

There are O(n²) centers, and each center may expand up to O(n) steps. Every step checks four directions.

This results in:

O(n³)

time complexity, which is too slow for n = 500.

Key Insight for an Optimal Solution

The crucial observation is:

The order of a plus sign at (r,c) equals the minimum number of consecutive 1s available in all four directions.

Instead of repeatedly expanding from every center, we can preprocess directional information.

For each cell, we want to know:

  • consecutive 1s to the left
  • consecutive 1s to the right
  • consecutive 1s upward
  • consecutive 1s downward

If a cell has:

left = 4
right = 3
up = 2
down = 5

Then the maximum plus order centered there is:

min(4,3,2,5) = 2

We can compute these values efficiently using four directional sweeps across the grid.

Dynamic programming works well here because each directional count depends only on the immediately previous cell in that direction.

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(n²) Expands outward from every center
Optimal O(n²) O(n²) Four directional passes using dynamic programming

Algorithm Walkthrough

Optimal Dynamic Programming Strategy

We maintain a matrix dp where:

dp[r][c]

stores the smallest directional arm length seen so far.

Initially, every non-mine cell starts with value n.

Then we perform four passes.

1. Build the Grid Representation

Convert mines into a hash set.

This allows constant time lookup:

(r, c) in mine_set

instead of repeatedly scanning mines.

We initialize:

dp[n][n]

with value n.

This matrix will gradually be refined.

2. Left-to-Right Pass

For each row:

  • Count consecutive 1s
  • Reset to 0 at mines

Example:

1 1 0 1 1

becomes:

1 2 0 1 2

We update:

dp[r][c] = min(dp[r][c], count)

We use min because later passes will further restrict the valid plus size.

3. Right-to-Left Pass

Repeat the process in reverse.

Example:

1 1 0 1 1

becomes:

2 1 0 2 1

Again update:

dp[r][c] = min(dp[r][c], count)

Now every cell knows its horizontal limitation.

4. Top-to-Bottom Pass

For each column:

Count consecutive 1s downward.

Example column:

1
1
0
1

becomes:

1
2
0
1

Update dp with minimum values.

5. Bottom-to-Top Pass

Repeat vertically upward.

This final pass gives every cell:

minimum(left, right, up, down)

That minimum directly equals the largest valid plus order centered there.

6. Track the Maximum

As we finish the final pass:

answer = max(answer, dp[r][c])

Return the largest order found.

Why it works

A valid plus sign requires equal arm reach in all four directions. Therefore, the limiting factor is always the shortest arm.

The four directional passes compute exactly how many consecutive 1s exist in every direction. Taking the minimum guarantees that all four arms can exist simultaneously.

Since every cell is evaluated independently and every directional count is exact, the algorithm always computes the correct largest plus sign.

Python Solution

from typing import List

class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
        mine_set = {(r, c) for r, c in mines}

        dp = [[n] * n for _ in range(n)]

        for row in range(n):
            count = 0
            for col in range(n):
                if (row, col) in mine_set:
                    count = 0
                else:
                    count += 1
                dp[row][col] = min(dp[row][col], count)

            count = 0
            for col in range(n - 1, -1, -1):
                if (row, col) in mine_set:
                    count = 0
                else:
                    count += 1
                dp[row][col] = min(dp[row][col], count)

        result = 0

        for col in range(n):
            count = 0
            for row in range(n):
                if (row, col) in mine_set:
                    count = 0
                else:
                    count += 1
                dp[row][col] = min(dp[row][col], count)

            count = 0
            for row in range(n - 1, -1, -1):
                if (row, col) in mine_set:
                    count = 0
                else:
                    count += 1
                dp[row][col] = min(dp[row][col], count)
                result = max(result, dp[row][col])

        return result

The implementation starts by converting mines into a hash set for constant time lookup. This avoids repeatedly searching through the mine list.

The dp matrix is initialized with value n because no plus sign can exceed the grid size. During each directional pass, we refine these values by taking the minimum.

The first two row sweeps compute left and right arm lengths. The second pair of column sweeps compute upward and downward arm lengths.

The bottom-to-top pass also updates the final answer because, by then, every cell contains the minimum of all four directional counts.

Go Solution

func orderOfLargestPlusSign(n int, mines [][]int) int {
	mineSet := make(map[[2]int]bool)

	for _, mine := range mines {
		mineSet[[2]int{mine[0], mine[1]}] = true
	}

	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
		for j := 0; j < n; j++ {
			dp[i][j] = n
		}
	}

	for row := 0; row < n; row++ {
		count := 0
		for col := 0; col < n; col++ {
			if mineSet[[2]int{row, col}] {
				count = 0
			} else {
				count++
			}

			if count < dp[row][col] {
				dp[row][col] = count
			}
		}

		count = 0
		for col := n - 1; col >= 0; col-- {
			if mineSet[[2]int{row, col}] {
				count = 0
			} else {
				count++
			}

			if count < dp[row][col] {
				dp[row][col] = count
			}
		}
	}

	result := 0

	for col := 0; col < n; col++ {
		count := 0
		for row := 0; row < n; row++ {
			if mineSet[[2]int{row, col}] {
				count = 0
			} else {
				count++
			}

			if count < dp[row][col] {
				dp[row][col] = count
			}
		}

		count = 0
		for row := n - 1; row >= 0; row-- {
			if mineSet[[2]int{row, col}] {
				count = 0
			} else {
				count++
			}

			if count < dp[row][col] {
				dp[row][col] = count
			}

			if dp[row][col] > result {
				result = dp[row][col]
			}
		}
	}

	return result
}

The Go implementation closely mirrors the Python version. Since Go does not have a built-in hash set, we simulate one using:

map[[2]int]bool

The dp matrix is represented using slices of slices. Integer overflow is not a concern because all values remain within the range [0, 500].

Worked Examples

Example 1

n = 5
mines = [[4,2]]

Grid:

Row Values
0 1 1 1 1 1
1 1 1 1 1 1
2 1 1 1 1 1
3 1 1 1 1 1
4 1 1 0 1 1

After horizontal passes:

Row DP Values
0 1 2 3 2 1
1 1 2 3 2 1
2 1 2 3 2 1
3 1 2 2 2 1
4 1 1 0 1 1

After vertical passes, center (2,2) becomes:

left = 3
right = 3
up = 3
down = 2

Therefore:

min(3,3,3,2) = 2

Largest order:

2

Example 2

n = 1
mines = [[0,0]]

Grid:

0

Every directional count becomes:

0

No plus sign exists.

Result:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n²) Four linear sweeps across an n × n grid
Space O(n²) DP matrix plus mine lookup set

The algorithm touches each cell a constant number of times. Even though there are four directional passes, each pass still processes every cell once, resulting in linear work relative to grid size:

4 × n² = O(n²)

The dp matrix dominates memory usage, requiring storage for every grid cell.

Test Cases

class Solution:
    def orderOfLargestPlusSign(self, n, mines):
        mine_set = {(r, c) for r, c in mines}

        dp = [[n] * n for _ in range(n)]

        for row in range(n):
            count = 0
            for col in range(n):
                if (row, col) in mine_set:
                    count = 0
                else:
                    count += 1
                dp[row][col] = min(dp[row][col], count)

            count = 0
            for col in range(n - 1, -1, -1):
                if (row, col) in mine_set:
                    count = 0
                else:
                    count += 1
                dp[row][col] = min(dp[row][col], count)

        result = 0

        for col in range(len(dp)):
            count = 0
            for row in range(len(dp)):
                if (row, col) in mine_set:
                    count = 0
                else:
                    count += 1
                dp[row][col] = min(dp[row][col], count)

            count = 0
            for row in range(len(dp) - 1, -1, -1):
                if (row, col) in mine_set:
                    count = 0
                else:
                    count += 1
                dp[row][col] = min(dp[row][col], count)
                result = max(result, dp[row][col])

        return result

sol = Solution()

assert sol.orderOfLargestPlusSign(5, [[4, 2]]) == 2  # provided example
assert sol.orderOfLargestPlusSign(1, [[0, 0]]) == 0  # fully mined single cell
assert sol.orderOfLargestPlusSign(1, []) == 1  # single open cell
assert sol.orderOfLargestPlusSign(2, []) == 1  # small full grid
assert sol.orderOfLargestPlusSign(3, []) == 2  # perfect centered plus
assert sol.orderOfLargestPlusSign(5, []) == 3  # maximum centered plus
assert sol.orderOfLargestPlusSign(3, [[1, 1]]) == 1  # center blocked
assert sol.orderOfLargestPlusSign(5, [[2, 1]]) == 2  # arm interruption
assert sol.orderOfLargestPlusSign(2, [[0, 0], [0, 1], [1, 0], [1, 1]]) == 0  # all mined
assert sol.orderOfLargestPlusSign(5, [[0, 2], [2, 0], [2, 4], [4, 2]]) == 2  # boundary interruptions
Test Why
n=5, [[4,2]] Verifies provided example
n=1, [[0,0]] Tests smallest grid with no plus sign
n=1, [] Tests smallest valid plus
n=2, [] Confirms no order 2 plus in tiny grid
n=3, [] Tests centered plus in odd-sized grid
n=5, [] Tests maximum plus in mine-free grid
n=3, [[1,1]] Ensures blocked center prevents large plus
n=5, [[2,1]] Verifies shortest arm determines order
fully mined 2x2 Confirms return 0
boundary interruptions Tests mines near edges

Edge Cases

Single Cell Grid

When n = 1, the grid contains only one position. If it is not mined, the answer is 1 because a single cell counts as a plus sign of order 1.

If the cell is mined, the answer becomes 0.

This case often causes off-by-one mistakes because arm length is k - 1, meaning order 1 requires no extension.

Center Blocked

A grid may visually appear capable of supporting a large plus sign, but if the center itself is mined, that plus sign is impossible.

For example:

1 1 1
1 0 1
1 1 1

The implementation handles this naturally because directional counts reset to 0 at mines, causing the center to contribute nothing.

One Direction Becomes the Bottleneck

A plus sign requires all four arms to exist equally. Even if three directions extend far, a single blocked direction limits the order.

Example:

1 1 1
1 1 0
1 1 1

The center cannot form a larger plus because the right arm is too short.

The algorithm correctly handles this by taking:

min(left, right, up, down)

which ensures the shortest arm determines the valid order.

Large Grid Near Constraint Limit

At n = 500, brute force expansion becomes prohibitively expensive.

The dynamic programming approach remains efficient because every cell is processed only a constant number of times, ensuring the algorithm scales comfortably within limits.