Leetcode Perfect Rectangle problem solution YASH PAL, 31 July 2024 In this Leetcode Perfect Rectangle problem solution, you have given an array of rectangles where rectangles[i] = [xi, yi, ai, bi] represents an axis-aligned rectangle. The bottom-left point of the rectangle is (xi, yi) and the top-right point of it is (ai, bi). Return true if all the rectangles together form an exact cover of a rectangular region. Problem solution in Python. class Solution: def isRectangleCover(self, rectangles: List[List[int]]) -> bool: area = 0 corners = set() a = lambda: (Y-y) * (X-x) for x, y, X, Y in rectangles: area += a() corners ^= {(x,y), (x,Y), (X,y), (X,Y)} if len(corners) != 4: return False x, y = min(corners, key=lambda x: x[0] + x[1]) X, Y = max(corners, key=lambda x: x[0] + x[1]) return a() == area Problem solution in Java. class Solution { public boolean isRectangleCover(int[][] rectangles) { if (rectangles == null || rectangles.length == 0 || rectangles[0].length == 0) { return false; } Set<int[]> set = new TreeSet<>((int[] a, int[] b) -> { if (a[3] <= b[1]) { return -1; } else if (a[1] >= b[3]) { return 1; } else if (a[2] <= b[0]) { return -1; } else if (a[0] >= b[2]) { return 1; } else return 0; }); int area = 0; int up = Integer.MIN_VALUE; int down = Integer.MAX_VALUE; int left = Integer.MAX_VALUE; int right = Integer.MIN_VALUE; for (int[] rect : rectangles) { area += (rect[2] - rect[0]) * (rect[3] - rect[1]); up = Math.max(up, rect[3]); right = Math.max(right, rect[2]); down = Math.min(down, rect[1]); left = Math.min(left, rect[0]); if (!set.add(rect)) { return false; } } if (!(((up - down) * (right - left)) == area)) return false; return true; } } Problem solution in C++. class Solution { public: Solution(){ vector<int> tmp(4,0); perfect_rect = tmp; } bool isRectangleCover(vector<vector<int>>& rectangles) { int minsum(INT_MAX),maxsum(INT_MIN); int subrectarea = 0; for(vector<int> rect : rectangles){ subrectarea += area(rect); if(rect[0]+rect[1] < minsum){ perfect_rect[0] = rect[0]; perfect_rect[1] = rect[1]; minsum = rect[0]+rect[1]; } if(rect[2]+rect[3] > maxsum){ perfect_rect[2] = rect[2]; perfect_rect[3] = rect[3]; maxsum = rect[2]+rect[3]; } } if(subrectarea != area(perfect_rect)) return false; for(vector<int> rect : rectangles){ VertexPos E; E = getVertexPos(rect[0],rect[1]); if(!checkVertexinMap(rect[0],rect[1],E)) return false; E = getVertexPos(rect[2],rect[1]); if(!checkVertexinMap(rect[2],rect[1],E)) return false; E = getVertexPos(rect[0],rect[3]); if(!checkVertexinMap(rect[0],rect[3],E)) return false; E = getVertexPos(rect[2],rect[3]); if(!checkVertexinMap(rect[2],rect[3],E)) return false; } for(auto it=EdgeMap.begin(); it!=EdgeMap.end(); it++) if(it->second != 2) return false; for(auto it=InsideMap.begin(); it!=InsideMap.end(); it++) if(it->second != 2 && it->second != 4) return false; return true; } private: vector<int> perfect_rect; enum VertexPos{Corner,Edge,Inside}; unordered_map<string,int> CornerMap; unordered_map<string,int> EdgeMap; unordered_map<string,int> InsideMap; bool checkVertexinMap(int x, int y, VertexPos v){ string s = to_string(x) + " " + to_string(y); if(v == Corner){ CornerMap[s]++; if(CornerMap[s]>1) return false; } else if(v == Edge){ EdgeMap[s]++; if(EdgeMap[s]>2) return false; } else{ InsideMap[s]++; if(InsideMap[s]>4) return false; } return true; } VertexPos getVertexPos(int x, int y){ int num = 0; if(x ==perfect_rect[0] || x == perfect_rect[2]) num++; if(y == perfect_rect[1] || y == perfect_rect[3]) num++; if(num==0) return Inside; else if(num==1) return Edge; return Corner; } int area(const vector<int>& rect){ return (rect[2]-rect[0])*(rect[3]-rect[1]); } }; coding problems