#764

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Largest Plus Sign

Find the largest axis-aligned plus sign in a binary grid with some mines using dynamic programming.

Problem Statement

You are given an integer n and an n x n binary grid where all values are initially 1's, except for the positions specified in the 'mines' array. Each element in the 'mines' array represents a position in the grid where the value is 0, indicating an obstacle. Your task is to find the order of the largest axis-aligned plus sign of 1's within the grid. If no such plus sign exists, return 0.

An axis-aligned plus sign of 1's has a center grid[r][c] == 1, with arms extending in all four directions (up, down, left, right). The length of each arm is the same, and the arms should only consist of 1's. The largest plus sign is determined by the minimum arm length at any center. You need to calculate the largest possible plus sign order and return it.

Examples

Example 1

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

Output: 2

In the above grid, the largest plus sign can only be of order 2. One of them is shown.

Example 2

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

Output: 0

There is no plus sign, so return 0.

Constraints

1 <= n <= 500
1 <= mines.length <= 5000
0 <= xi, yi < n
All the pairs (xi, yi) are unique.

Solution Approach

Dynamic Programming State Transition

For each grid cell, calculate the maximum number of consecutive 1's in all four directions (up, down, left, right). This can be achieved using dynamic programming arrays to store the consecutive 1's from each direction. For example, left[r][c] tracks the number of consecutive 1's to the left of cell (r, c) including itself, and similarly for the other directions.

Calculate the Plus Sign Order

Once we have the consecutive 1's for each direction, the size of the plus sign at each cell can be determined by taking the minimum of these values. The largest possible plus sign is the maximum of these minimum values across all grid cells.

Edge Case Handling

Handle edge cases such as small grids (n = 1), fully blocked grids, or grids with no possible plus sign. In these cases, the solution should return 0 if no valid plus sign can be formed.

Complexity Analysis

Metric	Value
Time	O(N^2)
Space	O(N^2)

The time complexity is O(N^2), where N is the size of the grid, because we need to process each cell in the grid for four directions. The space complexity is O(N^2) due to the need for dynamic programming tables to store the consecutive 1's in each direction for every cell.

What Interviewers Usually Probe

Can the candidate implement the dynamic programming approach efficiently?
Does the candidate handle edge cases such as fully blocked grids or small grids?
Is the candidate able to optimize the approach and avoid unnecessary recomputations?

Common Pitfalls or Variants

Common pitfalls

Not initializing the dynamic programming tables correctly for the four directions.
Overlooking edge cases where the grid is small or fully blocked.
Failing to correctly compute the minimum arm length for each center of a plus sign.

Follow-up variants

Change the grid size or mine distribution to test the scalability of the solution.
Modify the problem to allow arbitrary values in the grid (not just 1's and 0's).
Optimize for larger grids and more mines, while maintaining correctness.

FAQ

What is the largest plus sign problem about?

The problem asks you to find the largest order of an axis-aligned plus sign in a binary grid with obstacles (mines).

How do I approach solving this problem?

Use dynamic programming to compute consecutive 1's in all four directions (up, down, left, right) and determine the largest possible plus sign by taking the minimum of these values at each cell.

What is the primary pattern in solving the Largest Plus Sign problem?

The primary pattern is state transition dynamic programming, where the state of each cell is based on consecutive 1's from four directions.

What is the time complexity of the solution?

The time complexity is O(N^2) because we process each cell and calculate the consecutive 1's in four directions.

How does GhostInterview help with this problem?

GhostInterview helps by guiding you through the dynamic programming approach and optimizing solutions for edge cases and large grids.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
        dp = [[n] * n for _ in range(n)]
        for x, y in mines:
            dp[x][y] = 0
        for i in range(n):
            left = right = up = down = 0
            for j, k in zip(range(n), reversed(range(n))):
                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
                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)
        return max(max(v) for v in dp)

Continue Practicing

#773 sliding puzzle #746 min cost climbing stairs #741 cherry pickup