LeetCode 302: Smallest Rectangle Enclosing Black Pixels (Binary Search Boundaries)
English
Given one known black pixel (x,y), the black region is connected. We binary search four boundaries: top, bottom, left, right. Each boundary check scans one row or one column to see whether it contains any black pixel. Area is (bottom-top) * (right-left).
class Solution {
public int minArea(char[][] image, int x, int y) {
int m = image.length, n = image[0].length;
int top = searchRows(image, 0, x, true);
int bottom = searchRows(image, x + 1, m, false);
int left = searchCols(image, 0, y, top, bottom, true);
int right = searchCols(image, y + 1, n, top, bottom, false);
return (bottom - top) * (right - left);
}
private int searchRows(char[][] img, int lo, int hi, boolean findFirst) {
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
boolean hasBlack = false;
for (int c = 0; c < img[0].length; c++) {
if (img[mid][c] == '1') { hasBlack = true; break; }
}
if (hasBlack == findFirst) hi = mid;
else lo = mid + 1;
}
return lo;
}
private int searchCols(char[][] img, int lo, int hi, int top, int bottom, boolean findFirst) {
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
boolean hasBlack = false;
for (int r = top; r < bottom; r++) {
if (img[r][mid] == '1') { hasBlack = true; break; }
}
if (hasBlack == findFirst) hi = mid;
else lo = mid + 1;
}
return lo;
}
}class Solution:
def minArea(self, image: List[List[str]], x: int, y: int) -> int:
m, n = len(image), len(image[0])
def search_rows(lo: int, hi: int, find_first: bool) -> int:
while lo < hi:
mid = (lo + hi) // 2
has_black = any(image[mid][c] == '1' for c in range(n))
if has_black == find_first:
hi = mid
else:
lo = mid + 1
return lo
def search_cols(lo: int, hi: int, top: int, bottom: int, find_first: bool) -> int:
while lo < hi:
mid = (lo + hi) // 2
has_black = any(image[r][mid] == '1' for r in range(top, bottom))
if has_black == find_first:
hi = mid
else:
lo = mid + 1
return lo
top = search_rows(0, x, True)
bottom = search_rows(x + 1, m, False)
left = search_cols(0, y, top, bottom, True)
right = search_cols(y + 1, n, top, bottom, False)
return (bottom - top) * (right - left)中文
已知有一个黑点 (x,y)，并且所有黑点连通。可以分别对上、下、左、右四条边做二分查找。判断一行或一列是否包含黑点时，做一次线性扫描。最终最小包围矩形面积为 (bottom-top) * (right-left)。
class Solution {
public int minArea(char[][] image, int x, int y) {
int m = image.length, n = image[0].length;
int top = searchRows(image, 0, x, true);
int bottom = searchRows(image, x + 1, m, false);
int left = searchCols(image, 0, y, top, bottom, true);
int right = searchCols(image, y + 1, n, top, bottom, false);
return (bottom - top) * (right - left);
}
private int searchRows(char[][] img, int lo, int hi, boolean findFirst) {
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
boolean hasBlack = false;
for (int c = 0; c < img[0].length; c++) {
if (img[mid][c] == '1') { hasBlack = true; break; }
}
if (hasBlack == findFirst) hi = mid;
else lo = mid + 1;
}
return lo;
}
private int searchCols(char[][] img, int lo, int hi, int top, int bottom, boolean findFirst) {
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
boolean hasBlack = false;
for (int r = top; r < bottom; r++) {
if (img[r][mid] == '1') { hasBlack = true; break; }
}
if (hasBlack == findFirst) hi = mid;
else lo = mid + 1;
}
return lo;
}
}class Solution:
def minArea(self, image: List[List[str]], x: int, y: int) -> int:
m, n = len(image), len(image[0])
def search_rows(lo: int, hi: int, find_first: bool) -> int:
while lo < hi:
mid = (lo + hi) // 2
has_black = any(image[mid][c] == '1' for c in range(n))
if has_black == find_first:
hi = mid
else:
lo = mid + 1
return lo
def search_cols(lo: int, hi: int, top: int, bottom: int, find_first: bool) -> int:
while lo < hi:
mid = (lo + hi) // 2
has_black = any(image[r][mid] == '1' for r in range(top, bottom))
if has_black == find_first:
hi = mid
else:
lo = mid + 1
return lo
top = search_rows(0, x, True)
bottom = search_rows(x + 1, m, False)
left = search_cols(0, y, top, bottom, True)
right = search_cols(y + 1, n, top, bottom, False)
return (bottom - top) * (right - left)