Concise Binary Search Solution


  • 0
        public int minArea(char[][] image, int x, int y) {
            int v1 = binarySearch(image, 0, y, true, true);
            int v2 = binarySearch(image, y, image[0].length-1, true, false);
            int h1 = binarySearch(image, 0, x, false, true);
            int h2 = binarySearch(image, x, image.length-1, false, false);
            return (v2-v1+1)*(h2-h1+1);
        }
        public int binarySearch(char[][] image, int start, int end, boolean isVertical, boolean isLeft) {
            while(start<=end) {
                int mid = (end - start)/2 + start;
                boolean hasOne = searchLine(image, mid, isVertical);
                if(hasOne) {
                    start = isLeft? start: mid+1;
                    end = isLeft?mid-1: end;
                } else {
                    start = isLeft? mid+1: start;
                    end = isLeft? end: mid-1;
                }
            }
            return isLeft?start:end;
        }
        public boolean searchLine(char[][] image, int l, boolean isVertical) {
            int row = isVertical?0:l;
            int col = isVertical?l:0;
            while(row<image.length&&col<image[0].length) {
                if(image[row][col]=='1') return true;
                row += isVertical?1:0;
                col += isVertical?0:1;
            }
            return false;
        }
    

Log in to reply
 

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