C++ O(n) Solution


  • 1
    N

    All sub rectangles should follow the conditions:

    1. The sum of all rectangles area is equal to the perfect rectangle area.
    2. There are 4 vertices of a rectangle. Each vertex can be classified into 3 cases, depending on its position.
      a. The vertex lies in the corner of the perfect rectangle.
      b. The vertex lies in the edge of the perfect rectangle.
      c. The vertex is inside the perfect rectangle.

    Scan each vertex and find out which case it belongs to by function getVertexPos(int x, int y) , and store the vertex in the map and count it in function checkVertexinMap(int x, int y, VertexPos v). At last each vertex belongs to one or more subrectangles depending on its case.

    For case a, each vertex belongs to only 1 sub rectangle.
    For case b, each vertex belongs to 2 rectangles.
    For case c, each vertex belongs to 2 or 4 rectangles.

    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; // all values should be 1
        unordered_map<string,int> EdgeMap;   // all values should be 2
        unordered_map<string,int> InsideMap; // all values should be 2 or 4
        
        
        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;
        }
        
        //get the vertex position
        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]);
        }
    };
    

Log in to reply
 

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