Really Easy Understanding Solution(O(n), Java)


  • 148
    H

    The right answer must satisfy two conditions:

    1. the large rectangle area should be equal to the sum of small rectangles
    2. count of all the points should be even, and that of all the four corner points should be one
    public boolean isRectangleCover(int[][] rectangles) {
    
            if (rectangles.length == 0 || rectangles[0].length == 0) return false;
    
            int x1 = Integer.MAX_VALUE;
            int x2 = Integer.MIN_VALUE;
            int y1 = Integer.MAX_VALUE;
            int y2 = Integer.MIN_VALUE;
            
            HashSet<String> set = new HashSet<String>();
            int area = 0;
            
            for (int[] rect : rectangles) {
                x1 = Math.min(rect[0], x1);
                y1 = Math.min(rect[1], y1);
                x2 = Math.max(rect[2], x2);
                y2 = Math.max(rect[3], y2);
                
                area += (rect[2] - rect[0]) * (rect[3] - rect[1]);
                
                String s1 = rect[0] + " " + rect[1];
                String s2 = rect[0] + " " + rect[3];
                String s3 = rect[2] + " " + rect[3];
                String s4 = rect[2] + " " + rect[1];
                
                if (!set.add(s1)) set.remove(s1);
                if (!set.add(s2)) set.remove(s2);
                if (!set.add(s3)) set.remove(s3);
                if (!set.add(s4)) set.remove(s4);
            }
            
            if (!set.contains(x1 + " " + y1) || !set.contains(x1 + " " + y2) || !set.contains(x2 + " " + y1) || !set.contains(x2 + " " + y2) || set.size() != 4) return false;
            
            return area == (x2-x1) * (y2-y1);
        }
    

  • 0

    @hu19 Nice Solution and It is very easy to understand.


  • 5
    V

    Can you prove the input satisfy the two rules makes a perfect rectangle?


  • 1
    H

    said in Really Easy Understanding Solution(O(n), Java):

    the large rectangle area should be equal to the sum of small rectangles
    count of all the points should be even, and that of all the four corner points should be one

    I just want to ask, since I don't fully understand the problem, why the right answer must satisfy those two conditions you gave? Mind explaining your thought process?


  • 0
    M

    This is the easiest understanding solution. Thanks for sharing.


  • 1
    Y

    Very brilliant! Can you tell us how did you come up with this?


  • 1
    Z

    @hu19
    Hi hu19,
    "count of all the points should be even"---I think this is a redundant condition, if there are 4 points' count is one, and the large rectangle's area equal to the sum of all small rectangles, then we can guarantee it's a perfect rectangle.

    Correct me if I'm wrong. Hope to see some counterexamples.

    Thanks,


  • 0
    R

    @zhengpenghu
    Here is a counter example:
    [0,0,1,1]
    [0,2,1,3]
    [2,0,3,1]
    [2,2,3,3]
    [1,1,2,2]
    [1,1,2,2]
    [1,1,2,2]
    [1,1,2,2]
    [1,1,2,2]


  • 1
    R

    @hu19 Do you need the first condition here. Can you provide a counterexample?


  • 0
    R

    Never mind, If my understanding is correct, the size is used to remove the case such as internal small rectangles overlap with each other


  • 20
    F

    Thanks for sharing this nice solution. For those who are concerned with the validity of the two conditions, here is a quick proof.

    Proof to condition 1 is straightforward so I will focus on condition 2. First by observation we know it holds true for a perfect rectangle (consider how many small rectangles can overlap at a particular point: the number has to be even except for the four corner points of the prefect rectangle). The real question is whether it can also be true for some non-perfect rectangle.

    Let's begin with the question: what will a non-perfect rectangle look like? Of course it can look rather complicated but here is a simple way to define it: any non-perfect rectangle can be obtained by a sequence of adding or removing rectangular parts from its perfect counterpart (the order for adding or removing does not matter here). If condition 1 is held true, the non-perfect rectangle must be built by both adding and removing small rectangles such that the total area of added rectangles compensates for those of removed.

    Without loss of generality, let's focus on the first rectangle (denoted as FR) that is being removed (i.e., we have perfect rectangle before removing it). FR has four corner points. Before removing it, each corner points will appear even times (here I assume FR does not contain any corner points of the perfect rectangle. See my comment below for more details). After it's gone, all the four corner points will appear odd times. To make condition 2 valid again, for each of these four points, we have to either add or remove a rectangle such that each of them will once again appear even times. The key here is that the total number of rectangles added or removed is at least two, since the added or removed rectangles cannot overlap with FR, therefore each added or removed rectangle can contain at most two of the four corner points of FR.

    So we end up with at least two extra rectangles (either added or removed), with a total of eight corner points. Four of those points coincide with the four corner points of FR. What about the other four points? For each of these points, if it belongs to a rectangle that is being removed, then before removing, it must appear even times and after removing, it will appear odd times. If it belongs to a rectangle that is being added, no matter it coincides with any point in the perfect rectangle or not, its number of appearance will always be odd (appear once if does not coincide with any point, odd if it does since the original number of appearance before adding is even). In either case (adding or removing rectangle), there is no way to keep the number of appearance of all points even, therefore condition 2 cannot be true for non-perfect rectangles.


  • 0
    H

    @fun4LeetCode Thank you!


  • 0

    @Yanning I think this is a flavor of the Packing Problem which I believe what applications are using (for example) to fit horizontal and vertical photos side by side on your rectangle phone


  • 0
    M

    @fun4LeetCode
    the FR can contains one or two corner of the perfect rectangular, so "Before removing it, each corner points will appear even times" is not true


  • 1
    F

    @marcusgao94 Hi marcusgao94. Here "FR" only applies to those small rectangles that do not contain any of the corner points of the perfect rectangle. This is because we will check if all the four corner points are present at the end anyway, so it is assumed the non-perfect rectangle will have all the four corner points of its perfect counterpart.


  • 0
    J

    @fun4LeetCode Hi thank you for the explaination. I feel that there might be some missing conditions. Here is a counter example: What about the example where there are 9 rectangles : 2x{ (0,0,1,8), (1,0,7,1), (1,7,7,8), (7,0,8,8) } 1x (2,0,6,2)?

    Clearly, there are only 4 points with one count. Large rectangle area = 8x8 = sum of rectangles area. It satisfies the condition but is not a perfect rectangle.


  • 1
    F

    @jade86 Hi jade86. In your example, yes we do have 4 points with one count but they are not the 4 corner points of the perfect rectangle. So the test will fail when you check if all the four corner points are present at the end (i.e., in the original post, "if (!set.contains(x1 + " " + y1) || !set.contains(x1 + " " + y2) || !set.contains(x2 + " " + y1) || !set.contains(x2 + " " + y2) || set.size() != 4)" will be evaluated to be true).


  • 0
    J

    @fun4LeetCode I see! Thanks for the clarification!


  • 0

    You did a heck of a job! In this way, the problem is at most medium.


  • 0
    S

    @hu19 don't we need to add the set.size() == 4 as a condition to determine?


Log in to reply
 

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