O(n). 72%ile


  • 1
    P
    1. There should be exactly 4 points that occur once.
    2. The area should make sense. (overlap cases)
    3. Same rectangle should not occur more than once. ( this one fooled my program once. because all points are same, it bypasses case 1, and since the area is added twice, the missing portions get accounted for.)
    class Solution {
    public:
    struct pairhash {
        inline long long operator()(const std::pair<int,int> & v) const {
            return v.first*31+v.second;
        }
    };
        
        bool isRectangleCover(vector<vector<int>>& rectangles) {
            unordered_map<pair<int,int>, int,pairhash>umap;
            int totalA = 0;
            auto prev = vector<int>();
            //find points and add.
            for(auto &x : rectangles)
            {
                totalA += area(x); //add to the total area.
    
                if(x == prev) return false; // check if the rectangle repeated. If it did, return false.
                prev = x;
                //cout << area(x) << endl;
                searchAndAdd(x[0],x[1],umap);
                searchAndAdd(x[2],x[3],umap);
                searchAndAdd(x[2],x[1],umap);
                searchAndAdd(x[0],x[3],umap);
    
            }
            vector<pair<int,int>> sol;
            for(auto &x : umap)
            {
                if(x.second == 2)sol.push_back(x.first); //iterate the map once. and pull out the points which occured once.
            }
            if(sol.size() != 4) return false;
            sort(sol.begin(), sol.end());
            vector<int>a{sol[0].first,sol[0].second,sol[3].first,sol[3].second};
            auto fArea = area(a);
    
            if(totalA != fArea) return false;
            return true;
        }
        inline int area(vector<int>&x)
        {
            return abs((x[0] - x[2]) * (x[3] - x[1]));
        }
        void searchAndAdd(int &x, int &y,  unordered_map<pair<int,int>, int, pairhash> &umap)
        {
    //count the instances of the coordinate.
            auto a = make_pair(x,y);
            if(umap.find(a) != umap.end()) // contains! it.
            {
                umap[a] += 1;
            }
            else
            {
                umap[a] = 2;
            }
        }
        
    };

Log in to reply
 

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