1ms Concise Java Binary Search (DFS is 4ms)


  • 46

    If we don't know programming, how do we find the 4 boundaries given a black pixel?

    Do we need to search every black cell? Absolutely not.

    Intuitively, we would expand from the given 1 * 1 black cell, "aggressively" expand to the 4 boundaries, roughly half of the remaining space. If we don't "cut" any black pixel, we know we go too far and should go back half.

    This is exactly the process of binary search.

    One simple way without any worry about boundary, is as follows:

    • Use a vertical line, to jump to the leftmost black pixel , in the range of [0, y]
    • Use a vertical line, to jump to the rightmost black pixel, in the range of [y, n - 1]
    • Use a horizontal line, to jump to the topmost black pixel, in the range of [0, x]
    • Use a horizontal line, to jump to the bottommost black pixel, in the range of [x, m - 1]

    Hope it helps!

    public int minArea(char[][] image, int x, int y) {
        int left = leftmost(image, 0, y, true);
        int right = rightmost(image, y, image[0].length - 1, true);
        int top = leftmost(image, 0, x, false);
        int bottom = rightmost(image, x, image.length - 1, false);
        return (right - left + 1) * (bottom - top + 1);
    }
    
    int leftmost(char[][] image, int min, int max, boolean horizontal) {
        int l = min, r = max;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (!hasBlack(image, mid, horizontal)) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
    
    int rightmost(char[][] image, int min, int max, boolean horizontal) {
        int l = min, r = max;
        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if (!hasBlack(image, mid, horizontal)) {
                r = mid - 1;
            } else {
                l = mid;
            }
        }
        return r;
    }
    
    boolean hasBlack(char[][] image, int mid, boolean horizontal) {
        if (horizontal) {
            for (int i = 0; i < image.length; i++) {
                if (image[i][mid] == '1') {
                    return true;
                }
            }
        } else {
            for (int j = 0; j < image[0].length; j++) {
                if (image[mid][j] == '1') {
                    return true;
                }
            }
        }
        return false;
    }
    

    Version 2: Another harder but more compact way is as follows:
    public int minArea(char[][] image, int x, int y) {
        int m = image.length, n = image[0].length;
        int colMin = binarySearch(image, true, 0, y, 0, m, true);
        int colMax = binarySearch(image, true, y + 1, n, 0, m, false);
        int rowMin = binarySearch(image, false, 0, x, colMin, colMax, true);
        int rowMax = binarySearch(image, false, x + 1, m, colMin, colMax, false);
        return (rowMax - rowMin) * (colMax - colMin);
    }
    
    public int binarySearch(char[][] image, boolean horizontal, int lower, int upper, int min, int max, boolean goLower) {
        while(lower < upper) {
            int mid = lower + (upper - lower) / 2;
            boolean inside = false;
            for(int i = min; i < max; i++) {
                if((horizontal ? image[i][mid] : image[mid][i]) == '1') {
                    inside = true; 
                    break;
                }
            }
            if(inside == goLower) {
                upper = mid;
            } else {
                lower = mid + 1;
            }
        }
        return lower;
    }

  • 3
    M

    the approach dealing with boundaries is cool!
    upvoted.


  • 1
    J

    I was wondering why is the goLower variable necessary in this case? it seems like when goLower is true, we are finding the first white pixel next to a black pixel. Could someone explain? Thanks!


  • 0

    Great solution in generalizing search function, here is the inspired C++ version:

    class Solution { 
    public:
        int minArea(vector<vector<char>>& image, int x, int y) {
            if(!image.size() || !image[0].size()) return 0;
            int m = (int)image.size(), n = (int)image[0].size();
            int l = search(0, y, 0, m, image, true, '1');
            int r = search(y + 1, n, 0, m, image, true, '0');
            int u = search(0, x, l, r, image, false, '1');
            int d = search(x + 1, m, l, r, image, false, '0'); 
    
            return (r - l) * (d - u);
        }
    
        int search(int start, int end, int top, int bottom, vector<vector<char>>& image, bool hori, char target){
            while(start < end){
                int mid = start + (end - start) / 2, _top = top;
                char found = '0'; // if find any ‘1’ in search range [top, bottom), found = ‘1’
                while(_top < bottom){
                    if((hori ? image[_top++][mid] : image[mid][_top++]) == '1') {
                        found = '1'; 
                        break;
                    }
                }
                target == found ? end = mid : start = mid + 1;
            }
    
            return start;
        }
    };

  • 0
    P

    nice solution. just wondering why in rightmost function mid = l+(r-l+1)/2, but in leftmost function it is mid = l+(r-l)/2? what cause the different? thank


  • 0

    what is the time complexity of this method

    binary search is log(n) and each mid point we do a column/row search,
    so it is log(n)*n ? why this is faster than DFS which is log(n) ?
    can anyone explain thx


  • 1
    C

    @pinkdatura I have the same question, still no answer now?
    I modified the code, now both use (low + high) / 2

    private int leftMost(char[][] image, int low, int high, boolean horizontal){
            int mid = 0, res = high;
            while(low <= high){
                mid = (low + high) / 2;
                if(!hasBlack(image, mid, horizontal)){
                    low = mid + 1;
                }else{
                    res = Math.min(res, mid);
                    high = mid - 1;
                }
            }
            return res;
        }
        private int rightMost(char[][] image, int low, int high, boolean horizontal){
            int mid = 0, res = low;
            while(low <= high){
                mid = (low + high) / 2;
                if(!hasBlack(image, mid, horizontal)){
                    high = mid - 1;
                }else{
                    res = Math.max(res, mid);
                    low = mid+1;
                }
            }
            return res;
        }
    

    I insist on using the following binarysearch pattern in order to avoid any indexing problem

     while(low <= high){
                mid = (low + high) / 2;
                .....
                     high = mid - 1;
                .....
                     low = mid + 1;
                }
            }
    

  • 0
    C

    @三千世界 I think dfs is O(k) where k is the number of black points.


  • 1

    @cgxy1995 Same question here, I wrote my own code and there would be some index problem if we don't use mid = l+(r-l+1)/2, so I applied your solution, nice point on insisting on the binary search pattern


  • 0

    Rewrite some of this solution's logic to make it consistent for both binary search and readability.

    public class Solution {
        
        public int minArea(char[][] image, int x, int y) {
            int left = lowermost(image, 0, y, false);
            int right = uppermost(image, y, image[0].length - 1, false);
            int top = lowermost(image, 0, x, true);
            int bottom = uppermost(image, x, image.length - 1, true);
            return (right - left + 1) * (bottom - top + 1);
        }
        
        private int lowermost(char[][] image, int lo, int hi, boolean horizontalCut) {
            if(lo>hi)
                return lo;
            int mid = (lo + hi) / 2;
            if(cutBlack(image, mid, horizontalCut))
                return lowermost(image, lo, mid-1, horizontalCut);
            else
                return lowermost(image, mid+1, hi, horizontalCut);
        }
        
        private int uppermost(char[][] image, int lo, int hi, boolean horizontalCut) {
            if(lo>hi)
                return hi;
            int mid = (lo + hi) / 2;
            if(cutBlack(image, mid, horizontalCut))
                return uppermost(image, mid+1, hi, horizontalCut);
            else
                return uppermost(image, lo, mid-1, horizontalCut);
        }
        
        private boolean cutBlack(char[][] image, int k, boolean horizontalCut) {
            if(horizontalCut) {
                for(int i=0; i<image[0].length; i++)
                    if(image[k][i]=='1')
                        return true;
                return false;
            } else {
                for(int i=0; i<image.length; i++)
                    if(image[i][k]=='1')
                        return true;
                return false;
            }
        }
    }

  • 0
    F

    Same idea

    class Solution {
        public int minArea(char[][] image, int x, int y) {
            int row = image.length, col = image[0].length;
            int left = BinarySearchLeft(image, 0, y, true);
            int right = BinarySearchRight(image, y, col - 1, true);
            int top = BinarySearchLeft(image, 0, x, false);
            int bottom = BinarySearchRight(image, x, row - 1, false);
            return (right - left + 1) * (bottom - top + 1);
        }
        public int BinarySearchLeft(char[][] image, int left, int right, boolean vertical) {
            while (left + 1 < right) {
                int mid = (right - left) / 2 + left;
                if (hasBlack(image, mid, vertical)) {
                    right = mid;
                } else {
                    left = mid;
                }
            }
            if (hasBlack(image, left, vertical)) {
                return left;
            }
            return right;
        }
        public int BinarySearchRight(char[][] image, int left, int right, boolean vertical) {
            while (left + 1 < right) {
                int mid = (right - left) / 2 + left;
                if (hasBlack(image, mid, vertical)) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
            if (hasBlack(image, right, vertical)) {
                return right;
            }
            return left;
        }
        public boolean hasBlack(char[][] image, int x, boolean ver) {
            if (ver) {
                for (int i = 0; i < image.length; i++) {
                    if (image[i][x] == '1') return true;
                }
            } else {
                for (int i = 0; i < image[0].length; i++) {
                    if (image[x][i] == '1') return true;
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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