TomoLink
CompaniesZeptoData Structures & AlgorithmsLargest Plus Sign
DSA
MediumArray

Largest Plus Sign

arraydynamic programming

Problem Statement

You are given an integer n . You have an n x n binary grid grid with all values initially 1 's except for some indices given in the array mines . The i ^th element of the array mines is defined as mines[i] = [x _i , y _i ] where grid[x _i ][y _i ] == 0 .

Return the order of the largest axis-aligned plus sign of 1 's contained in grid . If there is none, return 0 .

An axis-aligned plus sign of 1 's of order k has some center grid[r][c] == 1 along with four arms of length k - 1 going up, down, left, and right, and made of 1 's. 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 1 's.

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 <= x _i , y _i < n
All the pairs (x _i , y _i ) are unique .
🤔
Medium
Difficulty
Topic Info
ModuleDSA
CategoryArray
Sub-topicDynamic Programming
Tags
arraydynamic programming
Navigation
Largest Plus Sign [Medium] | Zepto Dsa | TomoLink