C++/Java/Python Binary Search solution with explanation


  • 153

    Suppose we have a 2D array

    "000000111000000"
    "000000101000000"
    "000000101100000"
    "000001100100000"
    

    Imagine we project the 2D array to the bottom axis with the rule "if a column has any black pixel it's projection is black otherwise white". The projected 1D array is

    "000001111100000"
    

    Theorem

    If there are only one black pixel region, then in a projected 1D array all the black pixels are connected.

    Proof by contradiction

    Assume to the contrary that there are disconnected black pixels at i
    and j where i < j in the 1D projection array. Thus there exists one
    column k, k in (i, j) and and the column k in the 2D array has no
    black pixel. Therefore in the 2D array there exists at least 2 black
    pixel regions separated by column k which contradicting the condition
    of "only one black pixel region".

    Therefore we conclude that all the black pixels in the 1D projection
    array is connected.

    This means we can do a binary search in each half to find the boundaries, if we know one black pixel's position. And we do know that.

    To find the left boundary, do the binary search in the [0, y) range and find the first column vector who has any black pixel.

    To determine if a column vector has a black pixel is O(m) so the search in total is O(m log n)

    We can do the same for the other boundaries. The area is then calculated by the boundaries.
    Thus the algorithm runs in O(m log n + n log m)

    Java

    private char[][] image;
    public int minArea(char[][] iImage, int x, int y) {
        image = iImage;
        int m = image.length, n = image[0].length;
        int left = searchColumns(0, y, 0, m, true);
        int right = searchColumns(y + 1, n, 0, m, false);
        int top = searchRows(0, x, left, right, true);
        int bottom = searchRows(x + 1, m, left, right, false);
        return (right - left) * (bottom - top);
    }
    private int searchColumns(int i, int j, int top, int bottom, boolean opt) {
        while (i != j) {
            int k = top, mid = (i + j) / 2;
            while (k < bottom && image[k][mid] == '0') ++k;
            if (k < bottom == opt)
                j = mid;
            else
                i = mid + 1;
        }
        return i;
    }
    private int searchRows(int i, int j, int left, int right, boolean opt) {
        while (i != j) {
            int k = left, mid = (i + j) / 2;
            while (k < right && image[mid][k] == '0') ++k;
            if (k < right == opt)
                j = mid;
            else
                i = mid + 1;
        }
        return i;
    }
    //  Runtime: 1 ms
    

    C++

    vector<vector<char>> *image;
    int minArea(vector<vector<char>> &iImage, int x, int y) {
        image = &iImage;
        int m = int(image->size()), n = int((*image)[0].size());
        int top = searchRows(0, x, 0, n, true);
        int bottom = searchRows(x + 1, m, 0, n, false);
        int left = searchColumns(0, y, top, bottom, true);
        int right = searchColumns(y + 1, n, top, bottom, false);
        return (right - left) * (bottom - top);
    }
    int searchRows(int i, int j, int low, int high, bool opt) {
        while (i != j) {
            int k = low, mid = (i + j) / 2;
            while (k < high && (*image)[mid][k] == '0') ++k;
            if (k < high == opt)
                j = mid;
            else
                i = mid + 1;
        }
        return i;
    }
    int searchColumns(int i, int j, int low, int high, bool opt) {
        while (i != j) {
            int k = low, mid = (i + j) / 2;
            while (k < high && (*image)[k][mid] == '0') ++k;
            if (k < high == opt)
                j = mid;
            else
                i = mid + 1;
        }
        return i;
    }
    // Runtime: 20 ms
    

    Python

    def minArea(self, image, x, y):
        top = self.searchRows(image, 0, x, True)
        bottom = self.searchRows(image, x + 1, len(image), False)
        left = self.searchColumns(image, 0, y, top, bottom, True)
        right = self.searchColumns(image, y + 1, len(image[0]), top, bottom, False)
        return (right - left) * (bottom - top)
    
    def searchRows(self, image, i, j, opt):
        while i != j:
            m = (i + j) / 2
            if ('1' in image[m]) == opt:
                j = m
            else:
                i = m + 1
        return i
    
    def searchColumns(self, image, i, j, top, bottom, opt):
        while i != j:
            m = (i + j) / 2
            if any(image[k][m] == '1' for k in xrange(top, bottom)) == opt:
                j = m
            else:
                i = m + 1
        return i
    # Runtime: 56 ms
    

    Java (DRY)

    private char[][] image;
    public int minArea(char[][] iImage, int x, int y) {
        image = iImage;
        int m = image.length, n = image[0].length;
        int top = search(0, x, 0, n, true, true);
        int bottom = search(x + 1, m, 0, n, false, true);
        int left = search(0, y, top, bottom, true, false);
        int right = search(y + 1, n, top, bottom, false, false);
        return (right - left) * (bottom - top);
    }
    private boolean isWhite(int mid, int k, boolean isRow) {
        return ((isRow) ? image[mid][k] : image[k][mid]) == '0';
    }
    private int search(int i, int j, int low, int high, boolean opt, boolean isRow) {
        while (i != j) {
            int k = low, mid = (i + j) / 2;
            while (k < high && isWhite(mid, k, isRow)) ++k;
            if (k < high == opt)
                j = mid;
            else
                i = mid + 1;
        }
        return i;
    }
    //  Runtime: 2 ms
    

    C++ (DRY)

    vector<vector<char>> *image;
    int minArea(vector<vector<char>> &iImage, int x, int y) {
        image = &iImage;
        int m = int(image->size()), n = int((*image)[0].size());
        int top = search(0, x, 0, n, true, true);
        int bottom = search(x + 1, m, 0, n, false, true);
        int left = search(0, y, top, bottom, true, false);
        int right = search(y + 1, n, top, bottom, false, false);
        return (right - left) * (bottom - top);
    }
    bool isWhite(int mid, int k, bool isRow) {
        return ((isRow) ? (*image)[mid][k]:(*image)[k][mid]) == '0';
    }
    int search(int i, int j, int low, int high, bool opt, bool isRow) {
        while (i != j) {
            int k = low, mid = (i + j) / 2;
            while (k < high && isWhite(mid, k, isRow)) ++k;
            if (k < high == opt)
                j = mid;
            else
                i = mid + 1;
        }
        return i;
    }
    // Runtime: 24 ms
    

    Python (DRY, from Stefan's cool solution)

    def minArea(self, image, x, y):
        top = self.search(0, x, lambda mid: '1' in image[mid])
        bottom = self.search(x + 1, len(image), lambda mid: '1' not in image[mid])
        left = self.search(0, y, lambda mid: any(image[k][mid] == '1' for k in xrange(top, bottom)))
        right = self.search(y + 1, len(image[0]), lambda mid: all(image[k][mid] == '0' for k in xrange(top, bottom)))
        return (right - left) * (bottom - top)
    
    def search(self, i, j, check):
        while i != j:
            mid = (i + j) / 2
            if check(mid):
                j = mid
            else:
                i = mid + 1
        return i
    # Runtime: 56 ms
    

  • 1
    D

    "To find the left boundary, do the binary search in the [0,x) range and find the first column vector who has any black pixel."

    I think it works when the black pixels are connected in a row. How does it work when a row have disconnected black pixels? I guess I just don't understand how to get to the projection 1D array?


  • 0

    We can prove that "in a projected 1D array, all the black pixels are connected".

    Proof by contradiction
    see above


  • 0
    D

    Thanks for the explanation. I didn't see that the binary search was on the column, not on the row. This is a great solution.


  • 0

    Very great abstraction! And the following line of code is nice :-)

    if (k < high == opt)

  • 0
    J

    Just curious: even if not given the point (x, y), we can still use binary search to solve it and the time complexity is the same. Right?


  • 1

    if not given the point then you can not do a binary search. Consider a 1D problem with only 1 black pixel in the n pixels do you have a way to find it in O(logn) time? I think not.
    Again in a 2D array with only 1 black pixel in the nxn pixels do you have a way to find it in O(nlogn) time? I think neither.
    Therefore, I think without the given point, it will be O(n*m) in the worst case for any solution.


  • 0
    P

    this method has worst case of O(nlogm) right? where n is the longer side of rectangular.


  • -1

    what is the difference between if (k < high == opt) and if (k < high && opt)


  • 0

    Yes you are right. Asymptotically m log n is in O(n logm) for n > m.


  • 1

    (False && False) is False
    but
    (False == False) is True


  • 1

    Very nice solution!


  • 7
    T

    Idea and implementation are both brilliant!
    In a word, the algorithm is doing following:

    top = search row [0...x], find first row contain 1,
    bottom = search row[x+1, row], find first row contian all 0
    left = search col[0...y], find first col contain 1,
    right = search col[y+1, col], find first col contain all 0

  • 0
    O

    wow nice (y)


  • 0
    S

    I think if there's few black pixels in a big graph, DFS would be better. Anyone agree with me ?


  • 0

    i agree with you~

    However algorithm usually concern the worst case more often.

    Unless we were told that the input is sparse


  • 0
    Y

    "To determine if a column vector has a black pixel is O(m) so the search in total is O(m log n)"
    I dont get that. Yes you can search in log n after projecting into the first row, but you have to examine EVERY column to project. So projection can take M*N. I must miss something, could someone please explain to me?


  • 0
    Y

    Also I have an average O(N) solution. The idea is only doing dfs along the circumference, return if steped "inside" of "1"s.


  • 0
    Y

    Ah!I get the idea. we don't need to project every column. we jump and Only do log n time.


  • 0

    I am glad you helped yourself out~


Log in to reply
 

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