391. Perfect Rectangle

Given an array 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.

• line sweep solution
• Time : O(nlogn)
• Space : O(n)

class Solution {
public:
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        if(rectangles.size() == 1) return true;
        int area = 0, minx = INT_MAX, miny = INT_MAX, maxx = INT_MIN, maxy = INT_MIN;
        vector<array<int,4>> lines;
        for(auto& rec : rectangles) {
            minx = min(minx, rec[0]);
            miny = min(miny, rec[1]);
            maxx = max(maxx, rec[2]);
            maxy = max(maxy, rec[3]);
            
            lines.push_back({rec[0],1,rec[1],rec[3]});
            lines.push_back({rec[2],-1,rec[1],rec[3]});
            
            area += abs(rec[2] - rec[0]) * abs(rec[3] - rec[1]);
        }
        
        sort(lines.begin(), lines.end());
        set<pair<int, int>> s;
        for(auto& [_, flag, st, ed] : lines) {
            if(flag > 0) {
                auto it = s.lower_bound({st,ed});
                if(it != s.end() and it->first < ed) return false;
                if(it != s.begin() and (--it)->second > st) return false;
                s.insert({st,ed});
            } else s.erase({st,ed});
        }
        
        return area == abs(maxx - minx)*abs(maxy - miny);
    }
};

• hash table solution
• Time : O(n)
• Space : O(n)

class Solution {
    string makeKey(int a, int b) {
        return to_string(a) + '#' + to_string(b);
    }
public:
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        if(rectangles.size() == 1) return true;
        int area = 0, minx = INT_MAX, miny = INT_MAX, maxx = INT_MIN, maxy = INT_MIN;
        unordered_set<string> points;
        for(auto& rec : rectangles) {
            minx = min(minx, rec[0]);
            miny = min(miny, rec[1]);
            maxx = max(maxx, rec[2]);
            maxy = max(maxy, rec[3]);

            string k1 = makeKey(rec[0],rec[1]);
            string k2 = makeKey(rec[0],rec[3]);
            string k3 = makeKey(rec[2],rec[1]);
            string k4 = makeKey(rec[2],rec[3]);

            if(!points.insert(k1).second) points.erase(k1);
            if(!points.insert(k2).second) points.erase(k2);
            if(!points.insert(k3).second) points.erase(k3);
            if(!points.insert(k4).second) points.erase(k4);
            

            area += abs(rec[2] - rec[0]) * abs(rec[3] - rec[1]);
        }
        if(!points.count(makeKey(minx,miny)) ||!points.count(makeKey(minx,maxy)) ||!points.count(makeKey(maxx,miny)) ||!points.count(makeKey(maxx,maxy)) || points.size() != 4)
            return false;

        return area == abs(maxx - minx)*abs(maxy - miny);
    }
};