Simple O(n) solution for Perfect Rectangle problem


  • 1

    Solution is based on idea from https://discuss.leetcode.com/topic/55898/share-my-easy-way-to-approach-p1-including-p3-explanation.

    Main idea is that for final rectangle to not have gaps every corner must have "pair" corner from another rectangle. So each corner coordinate must appear % 2 == 0 times. The only exception is the 4 corner coordinates of convex hull rectangle. For rectangles not to have intersections we need to only check the total area.

    var getArea = function (r) {
        return (r[2] - r[0]) * (r[3] - r[1]);
    };
    
    /**
     * @param {number[][]} rectangles
     * @return {boolean}
     */
    var isRectangleCover = function(rectangles) {
        if (rectangles == null)
            return false;
        if (rectangles.length === 0)
            return true;
        
        let areaSum = 0;
        const hash = {};
        const r = [ ...rectangles[0] ];
        
        for (let i = 0; i < rectangles.length; i++) {
            const rect = rectangles[i];
            
            r[0] = Math.min(r[0], rect[0]);
            r[1] = Math.min(r[1], rect[1]);
            r[2] = Math.max(r[2], rect[2]);
            r[3] = Math.max(r[3], rect[3]);
            
            areaSum += getArea(rect);
    
            [ `${rect[0]}_${rect[1]}`,
              `${rect[0]}_${rect[3]}`,
              `${rect[2]}_${rect[1]}`,
              `${rect[2]}_${rect[3]}`,
            ].forEach((k) => {
                if (hash[k])
                    delete hash[k];
                else
                    hash[k] = 1;
            });
        }
        
        if (areaSum !== getArea(r))
            return false;
    
        if (Object.keys(hash).length !== 4)
            return false;
        
        if (hash[`${r[0]}_${r[1]}`] !== 1 ||
            hash[`${r[0]}_${r[3]}`] !== 1 ||
            hash[`${r[2]}_${r[1]}`] !== 1 ||
            hash[`${r[2]}_${r[3]}`] !== 1)
            return false;
    
        return true;
    };
    

  • 0

    Brilliant! Much better than my solution, but I have a hard time proving it. While it's obvious that for a cover without gaps there must be even number of each inner corner point, how to prove the converse? That is, that for every set of rectangles with the correct total area and even number of inner corners, there must be no gaps. It feels like it's correct, but how to prove it?

    It's obvious that it's possible to construct a cover with lots of gaps and even numbers of corners if you allow for incorrect area. Just double every rectangle, for example. The convex hull corners will be doubled then too, however.


  • 0

    @stachenov Thanks!

    I think we can prove this proposition: any cover with correct total area and a gap must have an inner point with odd number of corners. Idea is that any such cover can be fixed by "moving" intersected part to fill the gap. When you make such move you change evenness of gap corners and make then even when gap is fixed. So it must have been odd when gap wasn't fixed.

    So if our total area is correct and there is no inner points with odd number of corners then this cover has no gaps. And as the total area is correct it also has no intersections.


  • 0

    What puzzles me is this. When you move a corner to create a gap, you create oddness. But isn't it possible to compensate for that oddness by moving corners in such a fashion that it creates overlaps instead of violating evenness? I can't think of an example, and I don't think it's possible, but it still feels a bit foggy.


  • 0

    @stachenov Assume we have perfect rectangle cover. Let's say we move a 1x1 piece to create a gap. Then we can maintain evenness for 2 out of 4 gap corners at best (if we move it +1 or -1 by x or y).
    The case when we create several gaps is harder, but I think we can prove it for this case as well.


  • 0
    T

    @dettier I think the last if check is not required. As you are removing the entry from hashmap on finding a duplicate, and making sure only 4 number exists, then they are the extreme end points only. Correct me if I am wrong?

    if (hash[`${r[0]}_${r[1]}`] !== 1 ||
            hash[`${r[0]}_${r[3]}`] !== 1 ||
            hash[`${r[2]}_${r[1]}`] !== 1 ||
            hash[`${r[2]}_${r[3]}`] !== 1)
            return false;
    

  • 0

    @tareque_md You are probably right. I wasn't sure that those 4 points would definitely be the corners of the final rectangle. Couldn't prove that off the top of my head, so decided to add this check.


  • 0

    @tareque_md If you remove that test, the solution doesn't even get accepted by the OJ.


  • 0
    T

    @StefanPochmann I wonder why? The way above logic is coded , if only 4 points remain, then there count has to be 1. Can you think of a test case where it fails?


  • 0

    @tareque_md said in Simple O(n) solution for Perfect Rectangle problem:

    Can you think of a test case where it fails?

    The one you're shown when the submission doesn't get accepted?


  • 0

    @tareque_md The count should be one, right, but the check tests not only the count, but also what those 4 points are exactly. It may happen that there are 4 points remaining, but they are wrong points, not the corners of the bounding convex hull.

    It fails on this test: [[0,0,1,1],[0,0,2,1],[1,0,2,1],[0,2,2,3]]. Graphically, it looks something like this:

    3|
    2|11
    1|
    0|22
     -----
      0123
    

    Here, 22 corresponds to three rectangles, one 2x1 and two 1x1 on top of it, thus creating two layers of overlap. This overlap creates even number of corners, and therefore, the bottom rectangles are eliminated. The top is just a single 2x1 rectangle, so it remains in the hash set, leaving there exactly 4 corners. Only they are wrong corners.


Log in to reply
 

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