Java 108ms O(n) solution with explanation.


  • 0

    My idea is to check the area first. But this way cannot figure out if there is a hole inside the big rectangle and there is another overlapped area which fits in the hole.(Sadly I stuck on it for a long time during the contest and did not figure it out on time.)
    After reading the solution of using corners (O(n) solution by counting corners with detailed explaination by @hxtang ), I come up with a way to detect overlaps and combine with the area method above, it is the answer.

    For the area part, it is very simple. Go through the array. Calculate the sum of all the small rectangles and compare the sum with the area of the rectangle structs by the most left bottom point and the most right top point. If they do not equal, return false. If true, check corners. The reason I do not check both of them in one loop is I need to get the width of the big rectangle to form the value for hashset used below. In short, one loop, check area and get width.

    For checking corners, my idea is use 4 hashsets to store the coordinate of 4 corners of a rectangle. For the convenience, I combine the x,y coordinate into one integer (width is used here). Checking if two rectangles share the same top left, top right, bot left, bot right corner. Also, the number of outer corners need to be calculated since the big rectangle only contains 4 corners. For instance, while checking top left corner, if its value already exist in the top left set, return false, since two rectangles cannot share the same top left corner unless they overlap. Then if this value does not exist in any other hashsets, that means it is an outer corner, cornercount + 1. If one other hashset contains this value, means now it becomes a inner corner, cornercount - 1. If the value exists in more than one other hashset, that means it has already become an inner corner, there is no need to change cornercount. At the end, if the cornercount is 4, return true.

    The code is a little long since there are similar codes for 4 corners. But the idea is clear.

        public boolean isRectangleCover(int[][] rectangles) {
        //check area
        int[] twocorner = new int[4];
        twocorner[0] = rectangles[0][0];
        twocorner[1] = rectangles[0][1];
        twocorner[2] = rectangles[0][2];
        twocorner[3] = rectangles[0][3];
        int sumarea=0;
        for(int[] rect:rectangles){
            twocorner[0] = twocorner[0]<rect[0]?twocorner[0]:rect[0];
            twocorner[1] = twocorner[1]<rect[1]?twocorner[1]:rect[1];
            twocorner[2] = twocorner[2]>rect[2]?twocorner[2]:rect[2];
            twocorner[3] = twocorner[3]>rect[3]?twocorner[3]:rect[3];
            sumarea+=(rect[2]-rect[0])*(rect[3]-rect[1]);
        }
        int area = (twocorner[2]-twocorner[0])*(twocorner[3]-twocorner[1]);
        if(area!=sumarea) return false;
        //check corner
        int cornercount = 0;
        int width = twocorner[2]-twocorner[0] + 1;//this value is width + 1.
        Set<Integer> leftbot = new HashSet<>();
        Set<Integer> rightbot = new HashSet<>();
        Set<Integer> lefttop = new HashSet<>();
        Set<Integer> righttop = new HashSet<>();
        for(int[] rect:rectangles){
            //int[] lb = {rect[0],rect[1]};
            //int[] rt = {rect[2],rect[3]};
            //int[] lt = {rect[0],rect[3]};
            //int[] rb = {rect[2],rect[1]};
            int lb = (rect[1]-twocorner[1])*width + rect[0];
            int rt = (rect[3]-twocorner[1])*width + rect[2];
            int lt = (rect[3]-twocorner[1])*width + rect[0];
            int rb = (rect[1]-twocorner[1])*width + rect[2];
            if(leftbot.contains(lb)) return false;
            else{
                leftbot.add(lb);
                int tempcount = 0;
                if(rightbot.contains(lb)) tempcount++;
                if(lefttop.contains(lb)) tempcount++;
                if(righttop.contains(lb)) tempcount++;
                if(tempcount==0) cornercount++;
                if(tempcount==1) cornercount--;
            }
            if(lefttop.contains(lt)) return false;
            else{
                lefttop.add(lt);
                int tempcount = 0;
                if(rightbot.contains(lt)) tempcount++;
                if(leftbot.contains(lt)) tempcount++;
                if(righttop.contains(lt)) tempcount++;
                if(tempcount==0) cornercount++;
                if(tempcount==1) cornercount--;
            }
            if(rightbot.contains(rb)) return false;
            else{
                rightbot.add(rb);
                int tempcount = 0;
                if(leftbot.contains(rb)) tempcount++;
                if(lefttop.contains(rb)) tempcount++;
                if(righttop.contains(rb)) tempcount++;
                if(tempcount==0) cornercount++;
                if(tempcount==1) cornercount--;
            }
            if(righttop.contains(rt)) return false;
            else{
                righttop.add(rt);
                int tempcount = 0;
                if(rightbot.contains(rt)) tempcount++;
                if(lefttop.contains(rt)) tempcount++;
                if(leftbot.contains(rt)) tempcount++;
                if(tempcount==0) cornercount++;
                if(tempcount==1) cornercount--;
            }
        }
        if(cornercount!=4){
            return false;
        }
        return true;
    }

Log in to reply
 

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