O(n) solution by counting corners with detailed explaination


  • 60
    H

    This is an expanded version of my earlier post under the contest discussion board.
    The following code passes through not only the OJ but also various test cases others have pointed out.

    Idea

    0_1472399247817_perfect_rectangle.jpg

    Consider how the corners of all rectangles appear in the large rectangle if there's a perfect rectangular cover.
    Rule 1: The local shape of the corner has to follow one of the three following patterns

    • Corner of the large rectangle (blue): it occurs only once among all rectangles
    • T-junctions (green): it occurs twice among all rectangles
    • Cross (red): it occurs four times among all rectangles

    Rule 2: A point can only be the top-left corner of at most one sub-rectangle. Similarly it can be the top-right/bottom-left/bottom-right corner of at most one sub-rectangle. Otherwise overlaps occur.

    Proof of correctness

    Obviously, any perfect cover satisfies the above rules. So the main question is whether there exists an input which satisfy the above rules, yet does not compose a rectangle.

    First, any overlap is not allowed based on the above rules because

    • aligned overlap like [[0, 0, 1, 1], [0, 0, 2, 2]] are rejected by Rule 2.
    • unaligned overlap will generate a corner in the interior of another sub-rectangle, so it will be rejected by Rule 1.

    Second, consider the shape of boundary for the combined shape. The cross pattern does not create boundary. The corner pattern generates a straight angle on the boundary, and the T-junction generates a straight border.
    So the shape of the union of rectangles has to be rectangle(s).

    Finally, if there are more than two non-overlapping rectangles, at least 8 corners will be found, and cannot be matched to the 4 bounding box corners (be reminded we have shown that there is no chance of overlapping).
    So the cover has to be a single rectangle if all above rules are satisfied.

    Algorithm

    • Step1: Based on the above idea we maintain a mapping from (x, y)->mask by scanning the sub-rectangles from beginning to end.

      • (x, y) corresponds to corners of sub-rectangles
      • mask is a 4-bit binary mask. Each bit indicates whether there have been a sub-rectangle with a top-left/top-right/bottom-left/bottom-right corner at (x, y). If we see a conflict while updating mask, it suffice to return a false during the scan.
      • In the meantime we obtain the bounding box of all rectangles (which potentially be the rectangle cover) by getting the upper/lower bound of x/y values.
    • Step 2: Once the scan is done, we can just browse through the unordered_map to check the whether the mask corresponds to a T junction / cross, or corner if it is indeed a bounding box corner.
      (note: my earlier implementation uses counts of bits in mask to justify corners, and this would not work with certain cases as @StefanPochmann points out).

    Complexity

    The scan in step 1 is O(n) because it loop through rectangles and inside the loop it updates bounding box and unordered_map in O(1) time.

    Step2 visits 1 corner at a time with O(1) computations for at most 4n corners (actually much less because either corner overlap or early stopping occurs). So it's also O(n).

    // pos encoding: 1 - TL 2- TR 4- BL 8-BR
    // return false if a conflict in mask occurs (i.e. there used to be a rectangle with corner (x, y) at pos
    inline bool insert_corner(unordered_map<int, unordered_map<int, int>>& corner_count, int x, int y, int pos) {
        int& m = corner_count[x][y];
        if (m & pos) return false;
        m |= pos;
        return true;
    }
    
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        // step 1: counting
        unordered_map<int, unordered_map<int, int>> corner_count;
        int minx = INT_MAX, maxx=INT_MIN, miny=INT_MAX, maxy=INT_MIN;
        for (auto& rect : rectangles) {
            minx = min(minx, rect[0]);
            maxx = max(maxx, rect[2]);
            miny = min(miny, rect[1]);
            maxy = max(maxy, rect[3]);
            if (!insert_corner(corner_count, rect[0], rect[1], 1)) return false;
            if (!insert_corner(corner_count, rect[2], rect[1], 2)) return false;
            if (!insert_corner(corner_count, rect[0], rect[3], 4)) return false;
            if (!insert_corner(corner_count, rect[2], rect[3], 8)) return false;
        }
        
        //step2: checking
        bool valid_corner[16] = {false};
        bool valid_interior[16] = {false};
        valid_corner[1] = valid_corner[2] = valid_corner[4] = valid_corner[8] = true;
        valid_interior[3] = valid_interior[5] = valid_interior[10] = valid_interior[12] = valid_interior[15] = true;
        
        for (auto itx = corner_count.begin(); itx != corner_count.end(); ++itx) {
            int x = itx->first;
            for (auto ity = itx->second.begin(); ity != itx->second.end(); ++ity) {
                int y = ity->first;
                int mask = ity->second;
                if (((x != minx && x != maxx) || (y != miny && y != maxy)) && !valid_interior[mask]) 
                    return false;
            }
        }
        return true;
    }
    

    The above code may be refined by changing the 2D unordered_map to 1D. But such improvements has no effect on complexity.

    struct pairhash {//double hash function for pair key
    public:
        template <typename T, typename U>
        size_t operator()(const pair<T, U> &rhs) const {
            size_t l = hash<T>()(rhs.first);
            size_t r = hash<U>()(rhs.second);
            return l + 0x9e3779b9 + (r << 6) + (r >> 2);
        }
    };
    
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        // step 1: counting
        unordered_map<pair<int, int>, int, pairhash> corner_count;
        int minx = INT_MAX, maxx=INT_MIN, miny=INT_MAX, maxy=INT_MIN;
        for (auto& rect : rectangles) {
            minx = min(minx, rect[0]);
            maxx = max(maxx, rect[2]);
            miny = min(miny, rect[1]);
            maxy = max(maxy, rect[3]);
            
            int& m1 = corner_count[make_pair(rect[0], rect[1])]; 
            if (m1 & 1) return false; else m1 |= 1;
            int& m2 = corner_count[make_pair(rect[2], rect[1])];
            if (m2 & 2) return false; else m2 |= 2;
            int& m3 = corner_count[make_pair(rect[0], rect[3])]; 
            if (m3 & 4) return false; else m3 |= 4;
            int& m4 = corner_count[make_pair(rect[2], rect[3])]; 
            if (m4 & 8) return false; else m4 |= 8;
        }
        
        //step2: checking
        for (const auto& kv: corner_count) {
            pair<int, int> pos; int mask;
            tie(pos, mask) = kv;
            if ((pos.first != minx && pos.first != maxx) || (pos.second != miny && pos.second != maxy)) {
                if (mask != 3 && mask != 5 && mask != 10 && mask != 12 && mask != 15) return false;
            }
        }
        return true;
    }
    

  • 0

    @hxtang Nice solution and code. However, I would "create" the top-left and bottom-right points instead of passing the coordinates to insert_corner(), for better clarity.


  • 4

    It's wrong, fails for example [[0,0,1,1],[0,2,1,3],[1,1,2,2],[2,0,3,1],[2,2,3,3],[1,0,2,3],[0,1,3,2]].

    Update: Got fixed, doesn't fail that anymore. I'll try to find a new counterexample :-)


  • 0

    @StefanPochmann Thanks, just added your test case.


  • 0

    The idea is really clever! While, would you please explain why we need the mask, instead of only counting the number of occurrence of each point(1 at the outer-most corner, 2/4 for any other points).


  • 2

    @StefanPochmann For this case, will it be ok if we simply add another check about the size, as following?

    expectedSize = (maxx-minx) * (maxy-miny);
    actualSize = Sum(sub-rectangles)
    
    if(expectedSize == actualSize) return true;
    else return false;
    

  • 0
    H

    @StefanPochmann Thanks. I just updated the code to justify corners with mask directly, rather than with the counts. It passes all test cases now. Hopefully this is a correct version...


  • 0
    H

    @YuTingLiu The count does not uniquely determine the structure of the corner.
    E.g. [[0, 0, 3, 3], [1, 1, 2, 2], [1, 1, 2, 2]]
    Or see the failure case @StefanPochmann just pointed out.


  • 0

    @hxtang yeah, two sub-rectangle exists overlap


  • 0

    @hxtang did you update the code in your post?


  • 0
    H

    @agave I just did, to fix the issue pointed out above.


  • 0

    @hxtang also you need to invert green and red in your pic.


  • 0
    H

    @agave fixed, thanks.


  • 0
    L

    @hxtang In this line, int& m = corner_count[x][y];, if undefined behavior will occur if the map does not contain the element? Do you assume its value will be 0 if element is not in map?


  • 0
    H

    @liu6699002 The [] operator of unordered_map<KEY_TYPE, VALUE_TYPE> C++ inserts a new element (key, value) to the map if key does not exist, and value is returned from value default constructor of VALUE_TYPE.

    So when I call corner_count[x][y], if (x, y) both don't exist, it will first insert (x, unordered_map<int, int>{}) to corner_count, then insert (y, 0) to corner_count[x]. The value is initialized as 0 because value default constructor of int initializes its value to 0 under C++11 standard.


  • 0
    L

    @hxtang Why it will be initialized to 0? I think it will be uninitialized for int if it is an automatic (local) variable. Or 0 initialization will only work under C++ 11?


  • 0
    H

    @legesggg I was wrong in saying value is default constructed. It was actually value constructed.

    Check out the following post for the difference between default and value constructor.
    http://stackoverflow.com/questions/8860780/what-does-value-initializing-something-mean

    The short story is that unordered_map calls sth. like VALUE_TYPE value = VALUE_TYPE(); rather than VALUE_TYPE value; to construct the value.


  • 0
    L

    @hxtang A small comment: If my understanding of the code is correct, the position coding should be 1 - BL 2- BR 4- TL 8-TR for your code.


  • 0
    H

    @Longji It's probably due to a different definition of "top" and "bottom" for the coordinate system. I'm used to consider small y value to be at the top, like in an image.


  • 0
    M

    This is so smart! How did you think of the idea of transforming the problem to the validation of the corners? I am so amazed. I feed this is not only about how much you know about algorithm but also how smart and open-minded as an engineer! I was trying to solve this problem whole morning without getting anything useful. Sigh.


Log in to reply
 

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