Easy to understand O(n log(n)) solution in C++


  • 1
    A
    class Solution {
    public:
        bool isRectangleCover(vector<vector<int>>& rectangles) {
            
            sort(rectangles.begin(), rectangles.end());
            
            int n= rectangles.size();
            int x0, y0, x1, y1;
            int xmax = INT_MIN, ymax = INT_MIN, xmin = INT_MAX, ymin = INT_MAX;
            
            for(int i=0;i<n;i++)
            {
                xmax = max(xmax, rectangles[i][2]);
                ymax = max(ymax, rectangles[i][3]);
                xmin = min(xmin, rectangles[i][0]);
                ymin = min(ymin, rectangles[i][1]);
            }
            
            int area = 0;
            int totalarea = (xmax-xmin)*(ymax-ymin);
            
            set<pair<int, int>> mymap;
            
            pair<int, int> p00, p10, p01, p11;
            
            int i=0;
     // insert the first rectangle into the set
            x0 = rectangles[i][0];
            y0 = rectangles[i][1];
            x1 = rectangles[i][2];
            y1 = rectangles[i][3];
            
            p00 = make_pair(x0,y0);
            p01 = make_pair(x0,y1);
            p10 = make_pair(x1,y0);
            p11 = make_pair(x1,y1);
            
            mymap.insert(p00); mymap.insert(p01); mymap.insert(p10); mymap.insert(p11);
            area += (x1-x0)*(y1-y0);
            
            for(i=1;i<n;i++)
            {
            x0 = rectangles[i][0];
            y0 = rectangles[i][1];
            x1 = rectangles[i][2];
            y1 = rectangles[i][3];
            
            p00 = make_pair(x0,y0);
            p01 = make_pair(x0,y1);
            p10 = make_pair(x1,y0);
            p11 = make_pair(x1,y1);
            
            area += (x1-x0)*(y1-y0);
            
            if(mymap.find(p00) == mymap.end()) return false;
            mymap.erase(p00);
            if(mymap.find(p01) != mymap.end()) mymap.erase(p01);
            else mymap.insert(p01);
            if(mymap.find(p10) != mymap.end()) mymap.erase(p10);
            else mymap.insert(p10);
            if(mymap.find(p11) != mymap.end()) mymap.erase(p11);
            else mymap.insert(p11);
            }
    
            p00 = make_pair(xmin,ymin);
            p01 = make_pair(xmin,ymax);
            p10 = make_pair(xmax,ymin);
            p11 = make_pair(xmax,ymax);
            
            if((mymap.find(p00) == mymap.end())or(mymap.find(p01) == mymap.end())) return false;
            if((mymap.find(p10) == mymap.end())or(mymap.find(p11) == mymap.end())) return false;
    
            return ((mymap.size() == 4) and (area == totalarea));
            
        }
    };
    

    The main idea is that we maintain the boundary coordinates of the region formed so far in a set data structure. We can sort the array to see the operations more clearly. Whenever we add a new rectangle, we need to check that its bottom left vertex matches with a vertex in our set and then we remove it from the set.If it does not match we directly return false. We also need to check for other vertices and remove them if they exist or add them to the set if they don't.

    Finally, after we processes all vertices we need to check if we are left with a rectangle. In order for this to happen, the set size must be exactly 4. Our algorithm does not handle the cases when there is an overlap, but a simple area counter can detect such cases. We now have a complete O(n log(n)) algorithm.


  • 1

    It's wrong, fails for example [[0,0,1,2],[0,0,1,3],[1,2,2,3]].
    Update: the updated code doesn't fail this case anymore.


  • 0
    A
    This post is deleted!

  • 0
    A

    @StefanPochmann Wow, very nice example. Thanks for pointing out. I think that if I also check the values of the last 4 remaining vertices then it solves the problem. I changed the code to reflect this. Your thoughts?


  • 0

    @Adithya Might be correct now, or might just be harder to prove wrong :-)


  • 0
    A

    @StefanPochmann Well the thing with many of these solutions is that they are very intuitive but are tricky to prove, although I agree with you that proving them is important. I'll think of a proof and post it. Thanks for your comments :)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.