Why we need binary search or DFS?


  • 0
    Y

    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;
        }
    }

  • 0

    "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))

  • 1

    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.


  • 0
    Q

    Use quite similar idea and has the same question :)


Log in to reply
 

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