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'.1 <= x < m1 <= y < nimage[x][y] == '1'.- The black pixels in the
imageonly form one component.
Companies:
Google
Related Topics:
Array, Binary Search, Depth-First Search, Breadth-First Search, Matrix
// OJ: https://leetcode.com/problems/smallest-rectangle-enclosing-black-pixels/
// Author: github.com/lzl124631x
// Time: O(MlogN + NlogM)
// Space: O(M + N)
class Solution {
public:
int minArea(vector<vector<char>>& A, int x, int y) {
int M = A.size(), N = A[0].size();
auto getRowLength = [&]() {
int L = 0, R = x; // search min x
while (L <= R) {
int mid = (L + R) / 2, j = 0;
while (j < N && A[mid][j] == '0') ++j;
if (j < N) R = mid - 1;
else L = mid + 1;
}
int mn = L; // minX = L
L = x, R = M - 1;
while (L <= R) {
int mid = (L + R) / 2, j = 0;
while (j < N && A[mid][j] == '0') ++j;
if (j < N) L = mid + 1;
else R = mid - 1;
}
return L - mn; // maxX = R = L - 1
};
auto getColumnLength = [&]() {
int L = 0, R = y; // search min y
while (L <= R) {
int mid = (L + R) / 2, i = 0;
while (i < M && A[i][mid] == '0') ++i;
if (i < M) R = mid - 1;
else L = mid + 1;
}
int mn = L; // minY = L
L = y, R = N - 1;
while (L <= R) {
int mid = (L + R) / 2, i = 0;
while (i < M && A[i][mid] == '0') ++i;
if (i < M) L = mid + 1;
else R = mid - 1;
}
return L - mn; // maxX = R = L - 1
};
return getRowLength() * getColumnLength();
}
};Or
// OJ: https://leetcode.com/problems/smallest-rectangle-enclosing-black-pixels/
// Author: github.com/lzl124631x
// Time: O(MlogN + NlogM)
// Space: O(M + N)
class Solution {
public:
int minArea(vector<vector<char>>& A, int x, int y) {
int M = A.size(), N = A[0].size();
auto searchRow = [&](int L, int R, bool leftBound) {
while (L <= R) {
int mid = (L + R) / 2, j = 0;
while (j < N && A[mid][j] == '0') ++j;
if (j < N == leftBound) R = mid - 1;
else L = mid + 1;
}
return L;
};
auto searchColumn = [&](int L, int R, bool leftBound) {
while (L <= R) {
int mid = (L + R) / 2, i = 0;
while (i < M && A[i][mid] == '0') ++i;
if (i < M == leftBound) R = mid - 1;
else L = mid + 1;
}
return L;
};
return (searchRow(x, M - 1, false) - searchRow(0, x, true)) * (searchColumn(y, N - 1, false) - searchColumn(0, y, true));
}
};// OJ: https://leetcode.com/problems/smallest-rectangle-enclosing-black-pixels/
// Author: github.com/lzl124631x
// Time: O(MlogN + NlogM)
// Space: O(M + N)
class Solution {
public:
int minArea(vector<vector<char>>& A, int x, int y) {
int M = A.size(), N = A[0].size();
auto getRowLength = [&]() {
int L = 0, R = x; // search min x
while (L < R) {
int mid = (L + R) / 2, j = 0;
while (j < N && A[mid][j] == '0') ++j;
if (j < N) R = mid;
else L = mid + 1;
}
int mn = L; // minX = L
L = x, R = M - 1; // If we search for the maxX, the range should be [x, M - 1]
while (L < R) {
int mid = (L + R + 1) / 2, j = 0;
while (j < N && A[mid][j] == '0') ++j;
if (j < N) L = mid;
else R = mid - 1;
}
return L + 1 - mn; // maxX = L
};
auto getColumnLength = [&]() {
int L = 0, R = y; // search min y
while (L < R) {
int mid = (L + R) / 2, i = 0;
while (i < M && A[i][mid] == '0') ++i;
if (i < M) R = mid;
else L = mid + 1;
}
int mn = L; // minY = L
L = y, R = N - 1;
while (L < R) {
int mid = (L + R + 1) / 2, i = 0;
while (i < M && A[i][mid] == '0') ++i;
if (i < M) L = mid;
else R = mid - 1;
}
return L + 1 - mn; // maxX = L
};
return getRowLength() * getColumnLength();
}
};Or
// OJ: https://leetcode.com/problems/smallest-rectangle-enclosing-black-pixels/
// Author: github.com/lzl124631x
// Time: O(MlogN + NlogM)
// Space: O(M + N)
class Solution {
public:
int minArea(vector<vector<char>>& A, int x, int y) {
int M = A.size(), N = A[0].size();
auto getRowLength = [&]() {
int L = 0, R = x; // search min x
while (L < R) {
int mid = (L + R) / 2, j = 0;
while (j < N && A[mid][j] == '0') ++j;
if (j < N) R = mid;
else L = mid + 1;
}
int mn = L; // minX = L
L = x + 1, R = M; // If we search for the one after the maxX, the range should be `[x + 1, M]`.
while (L < R) {
int mid = (L + R) / 2, j = 0;
while (j < N && A[mid][j] == '0') ++j;
if (j < N) L = mid + 1;
else R = mid;
}
return L - mn; // maxX = L
};
auto getColumnLength = [&]() {
int L = 0, R = y; // search min y
while (L < R) {
int mid = (L + R) / 2, i = 0;
while (i < M && A[i][mid] == '0') ++i;
if (i < M) R = mid;
else L = mid + 1;
}
int mn = L; // minY = L
L = y + 1, R = N;
while (L < R) {
int mid = (L + R) / 2, i = 0;
while (i < M && A[i][mid] == '0') ++i;
if (i < M) L = mid + 1;
else R = mid;
}
return L - mn; // maxX = L
};
return getRowLength() * getColumnLength();
}
};We can shorten the 2nd version:
// OJ: https://leetcode.com/problems/smallest-rectangle-enclosing-black-pixels/
// Author: github.com/lzl124631x
// Time: O(MlogN + NlogM)
// Space: O(M + N)
class Solution {
public:
int minArea(vector<vector<char>>& A, int x, int y) {
int M = A.size(), N = A[0].size();
auto searchRow = [&](int L, int R, bool leftBound) {
while (L < R) {
int mid = (L + R) / 2, j = 0;
while (j < N && A[mid][j] == '0') ++j;
if (j < N == leftBound) R = mid;
else L = mid + 1;
}
return L;
};
auto searchColumn = [&](int L, int R, bool leftBound) {
while (L < R) {
int mid = (L + R) / 2, i = 0;
while (i < M && A[i][mid] == '0') ++i;
if (i < M == leftBound) R = mid;
else L = mid + 1;
}
return L;
};
return (searchRow(x + 1, M, false) - searchRow(0, x, true)) * (searchColumn(y + 1, N, false) - searchColumn(0, y, true));
}
};