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.

Leetcode Perfect Rectangle problem solution


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]);
    }
};