This is an expanded version of [my earlier post](https://discuss.leetcode.com/topic/55874/o-log-n-problem-2-and-o-n-problem-3-solution/3) under the contest discussion board.\nThe following code passes through not only the OJ but also various test cases others have pointed out.\n\n#### Idea\n![0_1472399247817_perfect_rectangle.jpg](/uploads/files/1472399247905-perfect_rectangle.jpg) \n\nConsider how the corners of all rectangles appear in the large rectangle if there's a perfect rectangular cover.\n**Rule 1:** The local shape of the corner has to follow one of the three following patterns\n* Corner of the large rectangle (blue): it occurs only once among all rectangles\n* T-junctions (green): it occurs twice among all rectangles\n* Cross (red): it occurs four times among all rectangles\n\n**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.\n\n#### Proof of correctness\nObviously, 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.\n\nFirst, ***any overlap is not allowed based on the above rules*** because\n- aligned overlap like [[0, 0, 1, 1], [0, 0, 2, 2]] are rejected by Rule 2.\n- unaligned overlap will generate a corner in the interior of another sub-rectangle, so it will be rejected by Rule 1.\n\nSecond, 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. \n***So the shape of the union of rectangles has to be rectangle(s).***\n\nFinally, 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). \n***So the cover has to be a single rectangle*** if all above rules are satisfied.\n\n#### Algorithm\n* **Step1:** Based on the above idea we maintain a mapping from (x, y)->mask by scanning the sub-rectangles from beginning to end. \n - (x, y) corresponds to corners of sub-rectangles\n - 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.\n - 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.\n\n* **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***.\n(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).\n\n#### Complexity\nThe 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.\n\nStep2 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).\n```\n// pos encoding: 1 - TL 2- TR 4- BL 8-BR\n// return false if a conflict in mask occurs (i.e. there used to be a rectangle with corner (x, y) at pos\ninline bool insert_corner(unordered_map>& corner_count, int x, int y, int pos) {\n int& m = corner_count[x][y];\n if (m & pos) return false;\n m |= pos;\n return true;\n}\n\nbool isRectangleCover(vector>& rectangles) {\n // step 1: counting\n unordered_map> corner_count;\n int minx = INT_MAX, maxx=INT_MIN, miny=INT_MAX, maxy=INT_MIN;\n for (auto& rect : rectangles) {\n minx = min(minx, rect[0]);\n maxx = max(maxx, rect[2]);\n miny = min(miny, rect[1]);\n maxy = max(maxy, rect[3]);\n if (!insert_corner(corner_count, rect[0], rect[1], 1)) return false;\n if (!insert_corner(corner_count, rect[2], rect[1], 2)) return false;\n if (!insert_corner(corner_count, rect[0], rect[3], 4)) return false;\n if (!insert_corner(corner_count, rect[2], rect[3], 8)) return false;\n }\n \n //step2: checking\n bool valid_corner[16] = {false};\n bool valid_interior[16] = {false};\n valid_corner[1] = valid_corner[2] = valid_corner[4] = valid_corner[8] = true;\n valid_interior[3] = valid_interior[5] = valid_interior[10] = valid_interior[12] = valid_interior[15] = true;\n \n for (auto itx = corner_count.begin(); itx != corner_count.end(); ++itx) {\n int x = itx->first;\n for (auto ity = itx->second.begin(); ity != itx->second.end(); ++ity) {\n int y = ity->first;\n int mask = ity->second;\n if (((x != minx && x != maxx) || (y != miny && y != maxy)) && !valid_interior[mask]) \n return false;\n }\n }\n return true;\n}\n```\n\nThe above code may be refined by changing the 2D unordered_map to 1D. But such improvements has no effect on complexity.\n```\nstruct pairhash {//double hash function for pair key\npublic:\n template \n size_t operator()(const pair &rhs) const {\n size_t l = hash()(rhs.first);\n size_t r = hash()(rhs.second);\n return l + 0x9e3779b9 + (r << 6) + (r >> 2);\n }\n};\n\nbool isRectangleCover(vector>& rectangles) {\n // step 1: counting\n unordered_map, int, pairhash> corner_count;\n int minx = INT_MAX, maxx=INT_MIN, miny=INT_MAX, maxy=INT_MIN;\n for (auto& rect : rectangles) {\n minx = min(minx, rect[0]);\n maxx = max(maxx, rect[2]);\n miny = min(miny, rect[1]);\n maxy = max(maxy, rect[3]);\n \n int& m1 = corner_count[make_pair(rect[0], rect[1])]; \n if (m1 & 1) return false; else m1 |= 1;\n int& m2 = corner_count[make_pair(rect[2], rect[1])];\n if (m2 & 2) return false; else m2 |= 2;\n int& m3 = corner_count[make_pair(rect[0], rect[3])]; \n if (m3 & 4) return false; else m3 |= 4;\n int& m4 = corner_count[make_pair(rect[2], rect[3])]; \n if (m4 & 8) return false; else m4 |= 8;\n }\n \n //step2: checking\n for (const auto& kv: corner_count) {\n pair pos; int mask;\n tie(pos, mask) = kv;\n if ((pos.first != minx && pos.first != maxx) || (pos.second != miny && pos.second != maxy)) {\n if (mask != 3 && mask != 5 && mask != 10 && mask != 12 && mask != 15) return false;\n }\n }\n return true;\n}\n```

Perfect Rectangle

Problem Description

Problem Description

Answer Panel