# Why we need binary search or DFS?

• If we are just finding a O(mn) solution, why not just simply scan it with largest range on each axis? it's even don't use x/y at all and beat half of solutions

``````public class Solution {
public int minArea(char[][] image, int x, int y) {
if (image.length == 0 || image[0].length == 0) {
return 0;
}
int n = image.length;
int m = image[0].length;
int lengthX = 0;
for (int j = 0; j < m; ++j) {
for (int i = 0; i < n; ++i) {
if (image[i][j] != '0') {
lengthX++;
break;
};
}
}
int lengthY = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (image[i][j] != '0') {
lengthY++;
break;
}
}
}
return lengthX * lengthY;
}
}``````

• "Why we need binary search or DFS?"

Who said we do?

I had posted a brute-force solution as well, but with your idea of just counting the rows/columns containing 1 it's even simpler now:

``````def minArea(self, image, x, y):
return sum('1' in r for r in image) * sum('1' in r for r in zip(*image))``````

• Binary search is not O(mn), it is O(mlogn+nlogm). In a square of n x n with n = 100000. O(mn) solution is no longer feasible, but BS can do just fine.

DFS in worst case is O(mn) however since it utilizing the x, y information it can handle cases where mn is large but the black region is rather small.

However I do think the Brute Force solution is fine in a interview as the first solution. Then we can discuss further optimization with the interviewer.

If you use x, y information, then i think DFS is no longer better than your solution even in the case with large mn and small black region.

PS: Your Brute Force is brilliant BTW~ :-) I like it.

• Use quite similar idea and has the same question :)

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