This post shares very detailed explanation of how to use binary search to find the boundaries of the smallest rectangle that encloses the black pixels.
The code is as follows.
1 class Solution { 2 public: 3 int minArea(vector<vector<char>>& image, int x, int y) { 4 int m = image.size(), n = image[0].size(); 5 int l = search(image, 0, x, 0, n, true, true); 6 int r = search(image, x + 1, m, 0, n, false, true); 7 int u = search(image, 0, y, l, r, true, false); 8 int d = search(image, y + 1, n, l, r, false, false); 9 return (r - l) * (d - u); 10 } 11 private: 12 bool white(vector<vector<char>>& image, int mid, int k, int row) { 13 return (row ? image[mid][k] : image[k][mid]) == '0'; 14 } 15 int search(vector<vector<char>>& image, int b, int e, int mini, int maxi, bool first, bool row) { 16 while (b != e) { 17 int mid = (b + e) / 2, k = mini; 18 while (k < maxi && white(image, mid, k, row)) k++; 19 if (k < maxi == first) e = mid; 20 else b = mid + 1; 21 } 22 return b; 23 } 24 };
I try to use short and meaningful names: l, r, u, d in minArea are for left, right, up, and down; b, e in search are for begin and end; mini and maxi are the ranges of the other variable; first means whether we search for the left/up or the right/down boundary; row means whether we search for the row or the column.
