Depth-First Search
Breadth-First Search
Array
Binary Search
Matrix
Description
You are given an m x n
binary matrix image
where 0
represents a white pixel and 1
represents a black pixel.
The black pixels are connected (i.e., there is only one black region). Pixels are connected horizontally and vertically.
Given two integers x
and y
that represents the location of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels .
You must write an algorithm with less than O(mn)
runtime complexity
Example 1:
Input: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
Output: 6
Example 2:
Input: image = [["1"]], x = 0, y = 0
Output: 1
Constraints:
m == image.length
n == image[i].length
1 <= m, n <= 100
image[i][j]
is either '0'
or '1'
.
0 <= x < m
0 <= y < n
image[x][y] == '1'.
The black pixels in the image
only form one component .
Solutions
Solution 1
Python3 Java C++ Go
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
39
40
41
42
43
44
45
46
47
48 class Solution :
def minArea ( self , image : List [ List [ str ]], x : int , y : int ) -> int :
m , n = len ( image ), len ( image [ 0 ])
left , right = 0 , x
while left < right :
mid = ( left + right ) >> 1
c = 0
while c < n and image [ mid ][ c ] == '0' :
c += 1
if c < n :
right = mid
else :
left = mid + 1
u = left
left , right = x , m - 1
while left < right :
mid = ( left + right + 1 ) >> 1
c = 0
while c < n and image [ mid ][ c ] == '0' :
c += 1
if c < n :
left = mid
else :
right = mid - 1
d = left
left , right = 0 , y
while left < right :
mid = ( left + right ) >> 1
r = 0
while r < m and image [ r ][ mid ] == '0' :
r += 1
if r < m :
right = mid
else :
left = mid + 1
l = left
left , right = y , n - 1
while left < right :
mid = ( left + right + 1 ) >> 1
r = 0
while r < m and image [ r ][ mid ] == '0' :
r += 1
if r < m :
left = mid
else :
right = mid - 1
r = left
return ( d - u + 1 ) * ( r - l + 1 )
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66 class Solution {
public int minArea ( char [][] image , int x , int y ) {
int m = image . length , n = image [ 0 ] . length ;
int left = 0 , right = x ;
while ( left < right ) {
int mid = ( left + right ) >> 1 ;
int c = 0 ;
while ( c < n && image [ mid ][ c ] == '0' ) {
++ c ;
}
if ( c < n ) {
right = mid ;
} else {
left = mid + 1 ;
}
}
int u = left ;
left = x ;
right = m - 1 ;
while ( left < right ) {
int mid = ( left + right + 1 ) >> 1 ;
int c = 0 ;
while ( c < n && image [ mid ][ c ] == '0' ) {
++ c ;
}
if ( c < n ) {
left = mid ;
} else {
right = mid - 1 ;
}
}
int d = left ;
left = 0 ;
right = y ;
while ( left < right ) {
int mid = ( left + right ) >> 1 ;
int r = 0 ;
while ( r < m && image [ r ][ mid ] == '0' ) {
++ r ;
}
if ( r < m ) {
right = mid ;
} else {
left = mid + 1 ;
}
}
int l = left ;
left = y ;
right = n - 1 ;
while ( left < right ) {
int mid = ( left + right + 1 ) >> 1 ;
int r = 0 ;
while ( r < m && image [ r ][ mid ] == '0' ) {
++ r ;
}
if ( r < m ) {
left = mid ;
} else {
right = mid - 1 ;
}
}
int r = left ;
return ( d - u + 1 ) * ( r - l + 1 );
}
}
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54 class Solution {
public :
int minArea ( vector < vector < char >>& image , int x , int y ) {
int m = image . size (), n = image [ 0 ]. size ();
int left = 0 , right = x ;
while ( left < right ) {
int mid = ( left + right ) >> 1 ;
int c = 0 ;
while ( c < n && image [ mid ][ c ] == '0' ) ++ c ;
if ( c < n )
right = mid ;
else
left = mid + 1 ;
}
int u = left ;
left = x ;
right = m - 1 ;
while ( left < right ) {
int mid = ( left + right + 1 ) >> 1 ;
int c = 0 ;
while ( c < n && image [ mid ][ c ] == '0' ) ++ c ;
if ( c < n )
left = mid ;
else
right = mid - 1 ;
}
int d = left ;
left = 0 ;
right = y ;
while ( left < right ) {
int mid = ( left + right ) >> 1 ;
int r = 0 ;
while ( r < m && image [ r ][ mid ] == '0' ) ++ r ;
if ( r < m )
right = mid ;
else
left = mid + 1 ;
}
int l = left ;
left = y ;
right = n - 1 ;
while ( left < right ) {
int mid = ( left + right + 1 ) >> 1 ;
int r = 0 ;
while ( r < m && image [ r ][ mid ] == '0' ) ++ r ;
if ( r < m )
left = mid ;
else
right = mid - 1 ;
}
int r = left ;
return ( d - u + 1 ) * ( r - l + 1 );
}
};
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60 func minArea ( image [][] byte , x int , y int ) int {
m , n := len ( image ), len ( image [ 0 ])
left , right := 0 , x
for left < right {
mid := ( left + right ) >> 1
c := 0
for c < n && image [ mid ][ c ] == '0' {
c ++
}
if c < n {
right = mid
} else {
left = mid + 1
}
}
u := left
left , right = x , m - 1
for left < right {
mid := ( left + right + 1 ) >> 1
c := 0
for c < n && image [ mid ][ c ] == '0' {
c ++
}
if c < n {
left = mid
} else {
right = mid - 1
}
}
d := left
left , right = 0 , y
for left < right {
mid := ( left + right ) >> 1
r := 0
for r < m && image [ r ][ mid ] == '0' {
r ++
}
if r < m {
right = mid
} else {
left = mid + 1
}
}
l := left
left , right = y , n - 1
for left < right {
mid := ( left + right + 1 ) >> 1
r := 0
for r < m && image [ r ][ mid ] == '0' {
r ++
}
if r < m {
left = mid
} else {
right = mid - 1
}
}
r := left
return ( d - u + 1 ) * ( r - l + 1 )
}
GitHub