# Java binary search O(nlogm + mlogn) runtime

• ``````public class Solution {
public int minArea(char[][] image, int x, int y) {
int m = image.length;
int n = image[0].length;
int start = y;// y is column
int end = n - 1;
int mid;
// find last column containing black pixel
while (start < end) {
mid = start + (end - start) / 2 + 1;
if (checkColumn(image, mid)) {
start = mid;
} else {
end = mid - 1;
}
}
int right = start;

start = 0;
end = y;
// find first column containing black pixel
while (start < end) {
mid = start + (end - start) / 2;
if (checkColumn(image, mid)) {
end = mid;
} else {
start = mid + 1;
}
}
int left = start;

start = x; // x is row
end = m - 1;
// find first row containing black pixel
while (start < end) {
mid = start + (end - start) / 2 + 1;
if (checkRow(image, mid)) {
start = mid;
} else {
end = mid - 1;
}
}
int down = start;

start = 0;
end = x;
// find first row containing black pixel
while (start < end) {
mid = start + (end - start) / 2;
if (checkRow(image, mid)) {
end = mid;
} else {
start = mid + 1;
}
}
int up = start;

return (right - left + 1) * (down - up + 1);
}

private boolean checkColumn(char[][] image, int col) {
for (int i = 0; i < image.length; i++) {
if (image[i][col] == '1') {
return true;
}
}
return false;
}

private boolean checkRow(char[][] image, int row) {
for (int j = 0; j < image[0].length; j++) {
if (image[row][j] == '1') {
return true;
}
}
return false;
}
}``````

• It's not O(logm + logn).

• is that O(mlogn + nlogm) ?

• This post is deleted!

• It's Mlog(N1N2)+Nlog(M1M2)

N1+N2=N = image.length M1+M2=M=image[0].length

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.