Short CPP Solution with Set


  • 0
    M

    It's wrong! See comments.

    Use two Sets to count individual corners. Complexity : O(NlogN).
    Got a TLE on Java with the same algorithm using HashSet :(

    class Solution {
    public:
        bool isRectangleCover(vector<vector<int>>& r) {
            set< pair<int,int> > h,hh;
            long long area;
            int n = r.size();
            int maxint = 2147483647;
            int ux = -maxint;
            int dx = maxint;
            int uy = -maxint;
            int dy = maxint;
            
            for (int i=0;i<n;i++)
            {
                for (int k1=0;k1<=2;k1+=2)
                    for (int k2=1;k2<=3;k2+=2)
                    {
                        pair<int,int> t = make_pair(r[i][k1],r[i][k2]);
                        if (h.find(t)!=h.end() && hh.find(t)!=hh.end()) hh.erase(hh.find(t));
                        else
                        {
                            h.insert(t);
                            hh.insert(t);
                        }
                    }
                ux = max(ux,r[i][2]);
                dx = min(dx,r[i][0]);
                uy = max(uy,r[i][3]);
                dy = min(dy,r[i][1]);
                area+=1LL*(r[i][2]-r[i][0])*(r[i][3]-r[i][1]);
            }
            
            if (area != 1LL*(ux-dx)*(uy-dy)) return false;
            return hh.size()==4;
            
        }
    };
    

  • 0

    It's wrong, fails for example [[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[2,2,3,3]].


  • 0
    M

    @StefanPochmann Very nice challenge. I guess the best solution is segment tree+linear scan.


  • 0
    M

    @StefanPochmann You can simplify the example to [[0,0,1,1],[0,0,1,1],[0,2,1,3]].


  • 0

    Thanks, added both of you and Stefan's test cases.


Log in to reply
 

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