Java O(n) solution by calculating area and counting vertex


  • 0
    X

    I think use class Pair can accelerate the solution.
    Here is my solution not fast...

    public class Solution {

    public boolean isRectangleCover(int[][] rectangles) {
        int minx=rectangles[0][0];
        int miny=rectangles[0][1];
        int maxx=rectangles[0][2];
        int maxy=rectangles[0][3];
        int len=rectangles.length;
        for(int i=1;i<len;i++){
            minx=Math.min(rectangles[i][0],minx);
            miny=Math.min(rectangles[i][1],miny);
            maxx=Math.max(rectangles[i][2],maxx);
            maxy=Math.max(rectangles[i][3],maxy);
        }
        int maxArea=(maxx-minx)*(maxy-miny);
        int sum=0;
        for(int i=0;i<len;i++){
            sum+=(rectangles[i][2]-rectangles[i][0])*(rectangles[i][3]-rectangles[i][1]);
        }
        if(sum!=maxArea){
            return false;
        }
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        int m=maxx-minx+1;
        for(int i=0;i<len;i++){
            int bl=m*(rectangles[i][1]-miny)+rectangles[i][0]-minx;
            int br=m*(rectangles[i][1]-miny)+rectangles[i][2]-minx;
            int tl=m*(rectangles[i][3]-miny)+rectangles[i][0]-minx;
            int tr=m*(rectangles[i][3]-miny)+rectangles[i][2]-minx;
            if(!map.containsKey(bl)){
                map.put(bl,1);
            }else{
                map.put(bl,map.get(bl)+1);
            }
            if(!map.containsKey(br)){
                map.put(br,1);
            }else{
                map.put(br,map.get(br)+1);
            }           
            if(!map.containsKey(tl)){
                map.put(tl,1);
            }else{
                map.put(tl,map.get(tl)+1);
            }      
            if(!map.containsKey(tr)){
                map.put(tr,1);
            }else{
                map.put(tr,map.get(tr)+1);
            }              
        }
        int vertex1=m*(miny-miny)+minx-minx;
        int vertex2=m*(maxy-miny)+minx-minx;
        int vertex3=m*(miny-miny)+maxx-minx;
        int vertex4=m*(maxy-miny)+maxx-minx;
        for(int key:map.keySet()){
            if(key==vertex1||key==vertex2||key==vertex3||key==vertex4){
                if(map.get(key)>1){
                    return false;
                }
            }else{
                if(map.get(key)%2==1){
                    return false;
                }
            }
        }
        return true;
    }

  • 0
    X
    This post is deleted!

Log in to reply
 

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