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

  • 6

    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:
    Clean and simple, please upvote, thanks!

  • -3

    @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

    how much hate do you have towards this world? Wait why do I even bother wasting time with this clownish man?

  • 0

    concise and elegant. thx!

  • 0

    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

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

  • 0

    @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.