Array
Dynamic Programming
Description
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 ith
element of the array mines
is defined as mines[i] = [xi , yi ]
where grid[xi ][yi ] == 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.
Example 1:
Input: n = 5, mines = [[4,2]]
Output: 2
Explanation: 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
Explanation: 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 .
Solutions
Solution 1
Python3 Java C++ Go
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 )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 class Solution {
public int orderOfLargestPlusSign ( int n , int [][] mines ) {
int [][] dp = new int [ n ][ n ] ;
for ( var e : dp ) {
Arrays . fill ( e , n );
}
for ( var e : mines ) {
dp [ e [ 0 ]][ e [ 1 ]] = 0 ;
}
for ( int i = 0 ; i < n ; ++ i ) {
int left = 0 , right = 0 , up = 0 , down = 0 ;
for ( int j = 0 , k = n - 1 ; j < n ; ++ j , -- k ) {
left = dp [ i ][ j ] > 0 ? left + 1 : 0 ;
right = dp [ i ][ k ] > 0 ? right + 1 : 0 ;
up = dp [ j ][ i ] > 0 ? up + 1 : 0 ;
down = dp [ k ][ i ] > 0 ? down + 1 : 0 ;
dp [ i ][ j ] = Math . min ( dp [ i ][ j ] , left );
dp [ i ][ k ] = Math . min ( dp [ i ][ k ] , right );
dp [ j ][ i ] = Math . min ( dp [ j ][ i ] , up );
dp [ k ][ i ] = Math . min ( dp [ k ][ i ] , down );
}
}
return Arrays . stream ( dp ). flatMapToInt ( Arrays :: stream ). max (). getAsInt ();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 class Solution {
public :
int orderOfLargestPlusSign ( int n , vector < vector < int >>& mines ) {
vector < vector < int >> dp ( n , vector < int > ( n , n ));
for ( auto & e : mines ) dp [ e [ 0 ]][ e [ 1 ]] = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
int left = 0 , right = 0 , up = 0 , down = 0 ;
for ( int j = 0 , k = n - 1 ; j < n ; ++ j , -- k ) {
left = dp [ i ][ j ] ? left + 1 : 0 ;
right = dp [ i ][ k ] ? right + 1 : 0 ;
up = dp [ j ][ i ] ? up + 1 : 0 ;
down = dp [ k ][ i ] ? down + 1 : 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 );
}
}
int ans = 0 ;
for ( auto & e : dp ) ans = max ( ans , * max_element ( e . begin (), e . end ()));
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 func orderOfLargestPlusSign ( n int , mines [][] int ) ( ans int ) {
dp := make ([][] int , n )
for i := range dp {
dp [ i ] = make ([] int , n )
for j := range dp [ i ] {
dp [ i ][ j ] = n
}
}
for _ , e := range mines {
dp [ e [ 0 ]][ e [ 1 ]] = 0
}
for i := 0 ; i < n ; i ++ {
var left , right , up , down int
for j , k := 0 , n - 1 ; j < n ; j , k = j + 1 , k - 1 {
left , right , up , down = left + 1 , right + 1 , up + 1 , down + 1
if dp [ i ][ j ] == 0 {
left = 0
}
if dp [ i ][ k ] == 0 {
right = 0
}
if dp [ j ][ i ] == 0 {
up = 0
}
if dp [ k ][ i ] == 0 {
down = 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 )
}
}
for _ , e := range dp {
ans = max ( ans , slices . Max ( e ))
}
return
}
GitHub