This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

In a 2D `grid`

from (0, 0) to (N-1, N-1), every cell contains a `1`

, except those cells in the given list `mines`

which are `0`

. What is the largest axis-aligned plus sign of `1`

s contained in the grid? Return the order of the plus sign. If there is none, return 0.

An "*axis-aligned plus sign of 1s* of order

`grid[x][y] = 1`

along with 4 arms of length `k-1`

going up, down, left, and right, and made of `1`

s. This is demonstrated in the diagrams below. Note that there could be `0`

s or `1`

s beyond the arms of the plus sign, only the relevant area of the plus sign is checked for 1s.

**Examples of Axis-Aligned Plus Signs of Order k:**

Order 1: 000 010 000 Order 2: 00000 00100 01110 00100 00000 Order 3: 0000000 0001000 0001000 0111110 0001000 0001000 0000000

**Example 1:**

Input:N = 5, mines = [[4, 2]]Output:2Explanation:11111 11111 1111111111 11011 In the above grid, the largest plus sign can only be order 2. One of them is marked in bold.

**Example 2:**

Input:N = 2, mines = []Output:1Explanation:There is no plus sign of order 2, but there is of order 1.

**Example 3:**

Input:N = 1, mines = [[0, 0]]Output:0Explanation:There is no plus sign, so return 0.

**Note:**

`N`

will be an integer in the range`[1, 500]`

.`mines`

will have length at most`5000`

.`mines[i]`

will be length 2 and consist of integers in the range`[0, N-1]`

.*(Additionally, programs submitted in C, C++, or C# will be judged with a slightly smaller time limit.)*

b'

\n\n#### Approach #1: Brute Force [Time Limit Exceeded]

\n

\n#### Approach #2: Dynamic Programming [Accepted]

\n

\n

'
**Intuition and Algorithm**

For each possible center, find the largest plus sign that could be placed by repeatedly expanding it.\nWe expect this algorithm to be , and so take roughly operations. This is a little bit too big for us to expect it to run in time.

\n\n**Complexity Analysis**

- \n
- \n
Time Complexity: , as we perform two outer loops (), plus the inner loop involving

\n`k`

is . \n - \n
Space Complexity: .

\n \n

\n

**Intuition**

How can we improve our bruteforce? One way is to try to speed up the inner loop involving `k`

, the order of the candidate plus sign.\nIf we knew the longest possible arm length in each direction from a center, we could know the order of a plus sign at that center. We could find these lengths separately using dynamic programming.

**Algorithm**

For each (cardinal) direction, and for each coordinate `(r, c)`

let\'s compute the `count`

of that coordinate: the longest line of `\'1\'`

s starting from `(r, c)`

and going in that direction.\nWith dynamic programming, it is either 0 if `grid[r][c]`

is zero, else it is `1`

plus the count of the coordinate in the same direction.\nFor example, if the direction is left and we have a row like `01110110`

, the corresponding count values are `01230120`

, and the integers are either 1 more than their successor, or 0.\nFor each square, we want `dp[r][c]`

to end up being the minimum of the 4 possible counts. At the end, we take the maximum value in `dp`

.

**Complexity Analysis**

- \n
- \n
Time Complexity: , as the work we do under two nested for loops is .

\n \n - \n
Space Complexity: , the size of

\n`dp`

. \n

\n

Analysis written by: @awice.

\n