My binary search solution


  • 0
    public int minArea(char[][] image, int x, int y) {
    	int tmp=x;
    	x=y;
    	y=tmp;
        int left=binarysearch(image,0,x,false,false);
        int right=binarysearch(image,x,image[0].length-1,false,true);
        int up=binarysearch(image,0,y,true,false);
        int down=binarysearch(image,y,image.length-1,true,true);
        return (right-left+1)*(down-up+1);
    }
    public int binarysearch(char[][] image,int lower,int upper,boolean isv,boolean isup)
    {
        int x=0;
        int y=0;
        while(lower<=upper)
        {
            int mid=lower+(upper-lower)/2;
            if(explore(image,mid,!isv)) 
            {
                if(isup) lower=mid+1;
                else upper=mid-1;
            }
            else 
            {
                if(isup) upper=mid-1;
                else lower=mid+1;
            }
        }
        return isup?lower-1:upper+1;
    }
    public boolean explore(char[][] image,int val,boolean isv)
    {
        int x=0,y=0;
        if(isv) x=val;
        else y=val;
        int len=isv?image.length:image[0].length;
        for(int i=0;i<len;i++)
        {
            if(isv) y=i;
            else x=i;
            if(image[y][x]=='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.