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.lengthn == image[i].length1 <= m, n <= 100image[i][j] is either '0' or '1'.0 <= x < m0 <= y < nimage[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)
}
|
