Smallest Rectangle Enclosing Black Pixels
Problem
Given a binary matrix where 1 marks black and the black pixels are connected, plus a known black-pixel position (x,y), return the area of the smallest axis-aligned rectangle enclosing all black pixels.
image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x=0, y=26def min_area(image, x, y):
m, n = len(image), len(image[0])
def bs(lo, hi, pred):
while lo < hi:
mid = (lo + hi) // 2
if pred(mid): hi = mid
else: lo = mid + 1
return lo
top = bs(0, x, lambda r: any(image[r][c] == "1" for c in range(n)))
bot = bs(x + 1, m, lambda r: not any(image[r][c] == "1" for c in range(n)))
left = bs(0, y, lambda c: any(image[r][c] == "1" for r in range(m)))
right = bs(y + 1, n, lambda c: not any(image[r][c] == "1" for r in range(m)))
return (bot - top) * (right - left)function minArea(image, x, y) {
const m = image.length, n = image[0].length;
const hasInRow = r => image[r].includes("1");
const hasInCol = c => image.some(r => r[c] === "1");
const bs = (lo, hi, pred) => { while (lo < hi) { const mid = (lo + hi) >> 1; pred(mid) ? hi = mid : lo = mid + 1; } return lo; };
const top = bs(0, x, hasInRow);
const bot = bs(x + 1, m, r => !hasInRow(r));
const left = bs(0, y, hasInCol);
const right = bs(y + 1, n, c => !hasInCol(c));
return (bot - top) * (right - left);
}class Solution {
char[][] img; int M, N;
public int minArea(char[][] image, int x, int y) {
img = image; M = image.length; N = image[0].length;
int top = bsRow(0, x, true), bot = bsRow(x + 1, M, false);
int left = bsCol(0, y, true), right = bsCol(y + 1, N, false);
return (bot - top) * (right - left);
}
boolean hasRow(int r) { for (int c = 0; c < N; c++) if (img[r][c] == '1') return true; return false; }
boolean hasCol(int c) { for (int r = 0; r < M; r++) if (img[r][c] == '1') return true; return false; }
int bsRow(int lo, int hi, boolean want) { while (lo < hi) { int m = (lo + hi) >>> 1; if (hasRow(m) == want) hi = m; else lo = m + 1; } return lo; }
int bsCol(int lo, int hi, boolean want) { while (lo < hi) { int m = (lo + hi) >>> 1; if (hasCol(m) == want) hi = m; else lo = m + 1; } return lo; }
}class Solution {
vector>* img; int M, N;
bool hasRow(int r) { for (int c = 0; c < N; c++) if ((*img)[r][c] == '1') return true; return false; }
bool hasCol(int c) { for (int r = 0; r < M; r++) if ((*img)[r][c] == '1') return true; return false; }
public:
int minArea(vector>& image, int x, int y) {
img = ℑ M = image.size(); N = image[0].size();
auto bs = [&](int lo, int hi, function p){ while (lo < hi) { int m = (lo + hi) / 2; p(m) ? hi = m : lo = m + 1; } return lo; };
int top = bs(0, x, [&](int r){ return hasRow(r); });
int bot = bs(x + 1, M, [&](int r){ return !hasRow(r); });
int left = bs(0, y, [&](int c){ return hasCol(c); });
int right = bs(y + 1, N, [&](int c){ return !hasCol(c); });
return (bot - top) * (right - left);
}
}; Explanation
The bounding rectangle is fully described by four numbers: the topmost and bottommost rows that contain black, and the leftmost and rightmost columns that contain black. We find each of these four edges with its own binary search.
Why does binary search work here? Because the black pixels are connected. If we project them onto the rows, the rows containing black form one unbroken block; same for columns. So "does this row contain any black pixel?" is a monotonic question we can bisect on, using the known black pixel at (x, y) as a fixed reference point.
For the top edge we search rows [0, x] for the first row that has a black pixel; for bot we search [x+1, m] for the first row that has none. The left and right edges work the same way on columns. The helper bs moves hi = mid when the predicate holds, else lo = mid + 1.
Example: image with black at rows 0..2 and columns 1..2, with (x, y) = (0, 2). The searches find top = 0, bot = 3, left = 1, right = 3, giving area (bot - top) * (right - left) = 3 * 2 = 6.
Each binary search scans a full row or column per probe, so the total cost is about (m + n) * log(mn) — much cheaper than checking every cell repeatedly.