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:
![](https://spcdn.pages.dev/leetcode/problems/0302.Smallest%20Rectangle%20Enclosing%20Black%20Pixels/images/pixel-grid.jpg)
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#
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)
}
|