Leetcode: Perfect Rectangle

This question is asked in Apple, Google, and Uber. 

Given an array rectangles where rectangles [xi, yi, ai, bi] represents an axis-aligned rectangle. The bottom left of the rectangle is (xi, yi) and the top right point of the rectangle is (ai, bi). No rectangles are allowed to overlap each other. 

For example, rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]] fits as a rectangle because all of the 5 rectangles cover a rectangular region. However, in the case of overlapping rectangle, rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]] fails to produce result as [1, 1, 3, 3,] and [2, 2, 4, 4] overlap each other. From this we can conclude that a rectangle will overlap each other if any data point x and y value is between the data point of the first rectangle and the data point of the second rectangle. 

So the right answer must satisfy 2 conditions:

1. the large rectangle area should be equal to the sum of all the small rectangles. 

2. Count of all the points should be even and the count of all of the 4 corner points should be 1. Here's why:

A point can cover one point (total of 2 as an edge) or 3 other points (total of 4 points as a corner). This image is very useful in the terms of understanding the algorithm:

A fast solution is to store a point object in set and initialize it as a separate class. Here's the final code: 

class Solution {

    static class Point {

        int x;

        int y;

        //x and y coordinates

        Point(int x, int y) {

            this.x = x;

            this.y = y; 

        }

        //see if the point equals object

        public boolean equals(Object o) {

            if(o instanceof Point) {

                Point p = (Point) o;

                return this.x == p.x && this.y = p.y;

            }

            return false;

        }

        //override hash function

        public int hashCode() {

            int code = 1; 

            code = code * 31 + x;

            code = code * 31 + y;

            return code; 

        }

    }

    public boolean isRectangleCover(int[][] rectangles) {

         //base null condition

        if(rectangles == null || rectangles.length == 0) return false;

        //set values to polar opposites of direction we reach

        int x1 = Integer.MAX_VALUE;

        int y1 = Integer.MAX_VALUE;

        int x2 = Integer.MIN_VALUE;

        int y2 = Integer.MIN_VALUE;

        int area = 0;

        //initialize hashset

        Set<Point> set = new HashSet<>(); 

        //for all the rectangles

        for(int[] rec : rectangles) {

            //calculate the area

            area += (rec[2] - rec[0]) * (rec[3] - rec[1]);

            //update all of the edge points

            x1 = Math.min(x1, rec[0]);

            y1 = Math.min(y1, rec[1]);

            x2 = Math.max(x2, rec[2]);

            y2 = Math.max(y2, rec[3]);

            //remove from the set if the set already contains the particular point 

            Point p1 = new Point(rec[0], rec[1]);

            if(!set.add(p1)) set.remove(p1);

            Point p2 = new Point(rec[0], rec[3]);

            if(!set.add(p2)) set.remove(p2);

            Point p3 = new Point(rec[2], rec[3]);

            if(!set.add(p3)) set.remove(p3);

            Point p4 = new Point(rec[2],  rec[1]);

            if(!set.add(p4)) set.remove(p4);

        }

            //now we make sure the set contains all the edge points

        if(set.size() != 4 || !set.contains(new Point(x1, y1))|| !set.contains(new Point(x1, y2)) || set.contains(new Point(x2, y2)) || set.contains(new Point(x2, y1))){

        return false;

    }

    //confirm the area is the same as covered in the edge points.

    return area == (x2 - x1) * (y2 - y1);

    }

}