Might be the simplest O(n) solution, only count corners,no area, no maxmin(with comments)


  • 6
    C

    Key idea: a perfect rectangle must have 4 corners

    public boolean isRectangleCover(int[][] rectangles) {
            Set<String> set = new HashSet<>();
            for(int[] rec: rectangles){
                //b = bottom, l = left, r = right, t = top
                //create corners with type
                String bl = rec[0]+","+rec[1]+"bl";
                String br = rec[2]+","+rec[1]+"br";
                String tl = rec[0]+","+rec[3]+"tl";
                String tr = rec[2]+","+rec[3]+"tr";
                //if these corners already exist, return false
                if(!set.add(bl) || !set.add(br) || !set.add(tl) || !set.add(tr)) return false;
                //if these 4 corners and previously added corners form a line, remove them
                if(set.remove(rec[0]+","+rec[1]+"tl")) set.remove(bl);
                else if(set.remove(rec[0]+","+rec[1]+"br")) set.remove(bl);
                if(set.remove(rec[2]+","+rec[1]+"bl")) set.remove(br);
                else if(set.remove(rec[2]+","+rec[1]+"tr")) set.remove(br);
                if(set.remove(rec[0]+","+rec[3]+"tr")) set.remove(tl);
                else if(set.remove(rec[0]+","+rec[3]+"bl")) set.remove(tl);
                if(set.remove(rec[2]+","+rec[3]+"tl")) set.remove(tr);
                else if(set.remove(rec[2]+","+rec[3]+"br")) set.remove(tr);
            }
            //a perfect rectangle contains 4 corners
            return set.size()==4;
        }
    

    A reference pic for the removal part:
    0_1478591653852_QQ截图20161105154102.png
    Clean and simple, please upvote, thanks!


  • -3
    M

    @cgxy1995 said in Might be the simplest O(n) solution, only count corners,no area, no maxmin(with comments):

    please upvote

    Begging like that always gets the opposite reaction from me...


  • 2
    C

    @ManuelP
    0_1478362606534_7.png
    0_1478362616787_2.png
    0_1478362689219_6.png
    0_1478362724772_3.png
    how much hate do you have towards this world? Wait why do I even bother wasting time with this clownish man?


  • 0
    P

    concise and elegant. thx!


  • 0
    I

    For a second I thought this solution was really brilliant and FAST because it's just O(n), then it turned out because of string creations on fly, it's soooo slow...


  • 1
    C

    exactly, for a job in reality it might be slow. But for an interview, I think this is the best solution.


  • 0
    M

    @cgxy1995 Why did you highlight that third "down"? I mean, since that downvote wasn't mine...


Log in to reply
 

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