Perfect Rectangle

Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.

Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Example 1:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [3,2,4,4],
  [1,3,2,4],
  [2,3,3,4]
]

Return true. All 5 rectangles together form an exact cover of a rectangular region.

Example 2:

rectangles = [
  [1,1,2,3],
  [1,3,2,4],
  [3,1,4,2],
  [3,2,4,4]
]

Return false. Because there is a gap between the two rectangular regions.

Example 3:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [3,2,4,4]
]

Return false. Because there is a gap in the top center.

Example 4:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [2,2,4,4]
]

Return false. Because two of the rectangles overlap with each other.

The problem is easy at first glance, but I missed lots of corner cases so I didn't crack it at first. There are quite a lot solutions online. And I find this one is the easiest. Basically, there should be only three types of points:

 


The blue ones are edge points, which form the four edges of the final rectangle (so yes, there should only be four). The green ones and red ones are inner points. So the idea is to use a set, for every point we have already seen (that's already in the set), we remove it from the set, otherwise we add the point to the set. After iterate all rectangles, all green and red points should be cancelled out and only four blue points should be in the set. Last step is to check if the area of the larger rectangle is equal to the sum of all smaller rectangles.

    public boolean isRectangleCover(int[][] rectangles) {
        if (rectangles.length == 0 || rectangles[0].length == 0) {
            return false;
        }
        int min_x = Integer.MAX_VALUE, max_x = Integer.MIN_VALUE, min_y = Integer.MAX_VALUE, max_y = Integer.MIN_VALUE;
        Set<string> set = new HashSet<>();
        int area = 0;
        for (int[] r : rectangles) {
            min_x = Math.min(r[0], min_x);
            min_y = Math.min(r[1], min_y);
            max_x = Math.max(r[2], max_x);
            max_y = Math.max(r[3], max_y);
            checkPoint(r[0], r[1], set);
            checkPoint(r[0], r[3], set);
            checkPoint(r[2], r[1], set);
            checkPoint(r[2], r[3], set);
            area += (r[2] - r[0]) * (r[3] - r[1]);
        }
        String m1 = getString(min_x, min_y);
        String m2 = getString(min_x, max_y);
        String m3 = getString(max_x, min_y);
        String m4 = getString(max_x, max_y);
        if (set.size() != 4 || !set.contains(m1) || !set.contains(m2) || !set.contains(m3) || !set.contains(m4)) {
            return false;
        }
        return area == (max_x - min_x) * (max_y - min_y);
        
    }
    
    private String getString(int x, int y) {
        return String.valueOf(x) + "-" + String.valueOf(y);
    }
    private void checkPoint(int x, int y, Set<string> set) {
        String s = getString(x, y);
        if (set.contains(s)) {
            set.remove(s);
        } else {
            set.add(s);
        }
    }