# 391. Perfect Rectangle

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 class Solution { public: bool isRectangleCover(vector>& rectangles) { int area = 0; int x1 = INT_MAX; int y1 = INT_MAX; int x2 = INT_MIN; int y2 = INT_MIN; unordered_set corners; for (const vector& r : rectangles) { area += (r[2] - r[0]) * (r[3] - r[1]); x1 = min(x1, r[0]); y1 = min(y1, r[1]); x2 = max(x2, r[2]); y2 = max(y2, r[3]); // Four points of current rectangle const vector points{to_string(r[0]) + " " + to_string(r[1]), to_string(r[0]) + " " + to_string(r[3]), to_string(r[2]) + " " + to_string(r[1]), to_string(r[2]) + " " + to_string(r[3])}; for (const string& point : points) if (!corners.insert(point).second) corners.erase(point); } if (corners.size() != 4) return false; if (!corners.count(to_string(x1) + " " + to_string(y1)) || !corners.count(to_string(x1) + " " + to_string(y2)) || !corners.count(to_string(x2) + " " + to_string(y1)) || !corners.count(to_string(x2) + " " + to_string(y2))) return false; return area == (x2 - x1) * (y2 - y1); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { public boolean isRectangleCover(int[][] rectangles) { int area = 0; int x1 = Integer.MAX_VALUE; int y1 = Integer.MAX_VALUE; int x2 = Integer.MIN_VALUE; int y2 = Integer.MIN_VALUE; Set corners = new HashSet<>(); for (int[] r : rectangles) { area += (r[2] - r[0]) * (r[3] - r[1]); x1 = Math.min(x1, r[0]); y1 = Math.min(y1, r[1]); x2 = Math.max(x2, r[2]); y2 = Math.max(y2, r[3]); // Four points of current rectangle String[] points = new String[] {r[0] + " " + r[1], // r[0] + " " + r[3], // r[2] + " " + r[1], // r[2] + " " + r[3]}; for (final String point : points) if (!corners.add(point)) corners.remove(point); } if (corners.size() != 4) return false; if (!corners.contains(x1 + " " + y1) || // !corners.contains(x1 + " " + y2) || // !corners.contains(x2 + " " + y1) || // !corners.contains(x2 + " " + y2)) return false; return area == (x2 - x1) * (y2 - y1); } }