Problem Description

You have an n x n binary grid that initially contains all 1s, except for certain positions specified in the mines array. Each element mines[i] = [xi, yi] indicates that grid[xi][yi] = 0.

Your task is to find the largest possible "plus sign" made of 1s in this grid. A plus sign is defined as:

• It has a center cell containing 1
• It has four arms extending up, down, left, and right from the center
• All cells in the arms must contain 1s
• The "order" of a plus sign is k, where the arms have length k - 1

For example, a plus sign of order 3 would look like:

    1
    1
1 1 1 1 1
    1
    1

The plus sign must be axis-aligned (arms extend horizontally and vertically only). The cells beyond the plus sign can be either 0s or 1s - they don't affect the validity of the plus sign.

Return the order of the largest plus sign that can be found in the grid. If no plus sign exists (all cells are 0s), return 0.

Example scenarios:

• In a 5x5 grid with no mines, the largest plus sign would have order 3 (center at position [2,2] with arms extending 2 cells in each direction)
• If mines block certain positions, the maximum plus sign order might be smaller
• A single 1 surrounded by 0s forms a plus sign of order 1

Intuition

The key insight is that for any cell to be the center of a plus sign of order k, it needs to have at least k-1 consecutive 1s extending in all four directions (up, down, left, right). The maximum order of a plus sign centered at any cell is limited by the shortest arm it can extend.

Think of it this way: if a cell can extend 5 cells to the left, 3 cells to the right, 4 cells up, and 6 cells down, the maximum plus sign centered at this cell would have order min(5, 3, 4, 6) = 3.

This naturally leads to a dynamic programming approach where for each cell, we need to calculate:

• How many consecutive 1s can we extend to the left (including itself)?
• How many consecutive 1s can we extend to the right?
• How many consecutive 1s can we extend upward?
• How many consecutive 1s can we extend downward?

The minimum of these four values gives us the maximum order of a plus sign centered at that cell.

The clever part of the solution is how it computes these four directional values efficiently. Instead of checking each cell independently four times, we can:

1. Process each row from left to right to compute left-extension values
2. Process each row from right to left to compute right-extension values
3. Process each column from top to bottom to compute up-extension values
4. Process each column from bottom to top to compute down-extension values

By using running counters that reset to 0 when we hit a mine and increment when we see a 1, we can compute all these values in a single pass through the grid. The dp[i][j] value is continuously updated to maintain the minimum of all four directional extensions, ultimately giving us the maximum plus sign order possible at each position.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses a dynamic programming approach with clever simultaneous computation of all four directional extensions.

Step 1: Initialize the DP table

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

We initialize a 2D array dp where each cell starts with value n (the maximum possible arm length). This represents the potential maximum plus sign order at each position.

Step 2: Mark the mines

for x, y in mines:
    dp[x][y] = 0

Set all mine positions to 0 since no plus sign can be centered at a mine.

Step 3: Process all four directions simultaneously

for i in range(n):
    left = right = up = down = 0
    for j, k in zip(range(n), reversed(range(n))):

For each row/column index i, we process:

• Row i from left to right (using index j from 0 to n-1)
• Row i from right to left (using index k from n-1 to 0)
• Column i from top to bottom (using index j)
• Column i from bottom to top (using index k)

Step 4: Count consecutive 1s in each direction

left = left + 1 if dp[i][j] else 0
right = right + 1 if dp[i][k] else 0
up = up + 1 if dp[j][i] else 0
down = down + 1 if dp[k][i] else 0

For each direction, we maintain a running counter:

• If the current cell is not a mine (value > 0), increment the counter
• If it's a mine (value = 0), reset the counter to 0

Step 5: Update DP values

dp[i][j] = min(dp[i][j], left)
dp[i][k] = min(dp[i][k], right)
dp[j][i] = min(dp[j][i], up)
dp[k][i] = min(dp[k][i], down)

For each cell, we keep the minimum of its current value and the newly computed directional extension. After processing all directions, dp[i][j] contains the maximum order of a plus sign that can be centered at position (i, j).

Step 6: Find the maximum

return max(max(v) for v in dp)

The answer is the maximum value in the entire dp table, representing the largest plus sign order possible in the grid.

Time Complexity: O(n²) - we visit each cell a constant number of times Space Complexity: O(n²) - for the dp table

Example Walkthrough

Let's walk through a small example with n = 5 and mines = [[4, 2]]:

Initial Grid (1s everywhere except mine at [4,2]):

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

Step 1: Initialize DP table with n=5:

dp = [[5, 5, 5, 5, 5],
      [5, 5, 5, 5, 5],
      [5, 5, 5, 5, 5],
      [5, 5, 5, 5, 5],
      [5, 5, 5, 5, 5]]

Step 2: Mark mine at [4,2]:

dp = [[5, 5, 5, 5, 5],
      [5, 5, 5, 5, 5],
      [5, 5, 5, 5, 5],
      [5, 5, 5, 5, 5],
      [5, 5, 0, 5, 5]]

Step 3: Process each i from 0 to 4:

When i = 0 (processing row 0 horizontally and column 0 vertically):

• Processing row 0 left-to-right: left counts = [1, 2, 3, 4, 5]
• Processing row 0 right-to-left: right counts = [5, 4, 3, 2, 1]
• Processing column 0 top-to-bottom: up counts = [1, 2, 3, 4, 5]
• Processing column 0 bottom-to-top: down counts = [5, 4, 3, 2, 1]

After updates:

dp = [[1, 2, 3, 4, 5],
      [2, 5, 5, 5, 5],
      [3, 5, 5, 5, 5],
      [4, 5, 5, 5, 5],
      [5, 5, 0, 5, 5]]

When i = 4 (processing row 4 with the mine):

• Processing row 4 left-to-right:

  • j=0: left=1, dp[4][0] = min(5, 1) = 1
  • j=1: left=2, dp[4][1] = min(2, 2) = 2
  • j=2: left=0 (mine), dp[4][2] = min(0, 0) = 0
  • j=3: left=1, dp[4][3] = min(1, 1) = 1
  • j=4: left=2, dp[4][4] = min(1, 2) = 1

• Processing row 4 right-to-left:

  • k=4: right=1, dp[4][4] = min(1, 1) = 1
  • k=3: right=2, dp[4][3] = min(1, 2) = 1
  • k=2: right=0 (mine), dp[4][2] = min(0, 0) = 0
  • k=1: right=1, dp[4][1] = min(2, 1) = 1
  • k=0: right=2, dp[4][0] = min(1, 2) = 1

Final DP table after all processing:

dp = [[1, 1, 1, 1, 1],
      [1, 2, 2, 2, 1],
      [1, 2, 3, 2, 1],
      [1, 2, 2, 2, 1],
      [1, 1, 0, 1, 1]]

Result: The maximum value in dp is 3 (at position [2,2]).

This means we can form a plus sign of order 3 centered at [2,2]:

    1
    1
1 1 1 1 1
    1
    1

The mine at [4,2] prevents any larger plus signs from forming, as it blocks the downward arm of any plus sign centered above it in column 2.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The algorithm uses a nested loop structure where:

• The outer loop runs n times (iterating through each row/column index i)
• The inner loop runs n times for each outer loop iteration (iterating through index j and k simultaneously)
• Inside the inner loop, all operations (comparisons, assignments, min operations) are O(1)
• The initial setup of the dp array takes O(n²) time
• Setting mines in the dp array takes O(m) time where m is the number of mines, but m ≤ n²
• The final operation to find the maximum value requires traversing the entire dp array, which is O(n²)

Therefore, the overall time complexity is O(n²) + O(m) + O(n²) + O(n²) = O(n²)

Space Complexity: O(n²)

The space usage includes:

• A 2D dp array of size n × n, which requires O(n²) space
• Four auxiliary variables (left, right, up, down) which require O(1) space
• Loop variables and other temporary variables require O(1) space

Therefore, the overall space complexity is O(n²)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Order Definition

A common mistake is confusing the "order" of a plus sign with its arm length. The order k means the arms extend k-1 cells from the center, not k cells. For example:

• Order 1: Just the center cell (no arms extending)
• Order 2: Center + 1 cell in each direction
• Order 3: Center + 2 cells in each direction

Solution: Remember that the order equals the number of consecutive 1s in each direction (including the center), which is why the code counts consecutive 1s rather than arm lengths.

2. Incorrect Initialization of the DP Table

Some might initialize the DP table with 0s or 1s instead of n. This would break the algorithm because:

• We need to track the minimum arm length across all four directions
• Starting with 0 would prevent any meaningful updates
• Starting with 1 would limit the maximum possible plus sign size

Solution: Initialize with n (the maximum possible value) so that the min() operations can properly reduce it based on actual constraints.

3. Processing Directions Sequentially Instead of Simultaneously

A tempting but incorrect approach would be to process each direction in separate loops:

# WRONG APPROACH
for i in range(n):
    for j in range(n):
        # Calculate left arm
      
for i in range(n):
    for j in range(n):
        # Calculate right arm
# etc.

This would require multiple passes and complicate the logic for maintaining consecutive counts.

Solution: The clever use of zip(range(n), reversed(range(n))) allows processing opposite directions in a single pass, maintaining the consecutive count efficiently.

4. Forgetting to Reset Consecutive Counts at Mines

When encountering a mine (0 value), the consecutive count must reset to 0, not continue or decrement. Missing this reset would incorrectly calculate arm lengths across mines:

# WRONG: Just decrementing or not updating
consecutive_left = consecutive_left - 1 if max_arm_length[i][j] == 0 else consecutive_left + 1

# CORRECT: Reset to 0 at mines
consecutive_left = consecutive_left + 1 if max_arm_length[i][j] != 0 else 0

Solution: Always reset the counter to 0 when encountering a mine to ensure arms don't "jump over" blocked cells.

5. Overwriting Values Before They're Used

Since we're updating the same DP table we're reading from, there's a risk of using already-modified values. However, the algorithm cleverly avoids this by:

• Only updating with min() operations (never increasing values)
• Processing each direction's updates to different cells in the correct order

Solution: The algorithm's design inherently avoids this issue, but if modifying the approach, be careful about the order of reads and writes to ensure you're using the correct values for calculations.