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.

Solution

public class Solution {

    Map<Integer, Map<Integer, Integer>> map = new HashMap<Integer, Map<Integer, Integer>>();
    public boolean isRectangleCover(int[][] rec) {
        if(rec.length == 0) return false;

        int minX = rec[0][0];
        int maxX = rec[0][0];
        int minY = rec[0][1];
        int maxY = rec[0][1];
        int area = 0;

        for(int i = 0; i < rec.length; i++) {
            if(!setBit(rec[i][0], rec[i][1], 1 << 0)) return false; // bottom-left
            if(!setBit(rec[i][2], rec[i][1], 1 << 1)) return false; // bottom-right
            if(!setBit(rec[i][0], rec[i][3], 1 << 2)) return false; // top-left
            if(!setBit(rec[i][2], rec[i][3], 1 << 3)) return false; // top-right
            area += (rec[i][2] - rec[i][0]) * (rec[i][3] - rec[i][1]);

            minX = Integer.min(minX, rec[i][0]);
            maxX = Integer.max(maxX, rec[i][2]);

            minY = Integer.min(minY, rec[i][1]);
            maxY = Integer.max(maxY, rec[i][3]);
        }

        // check area
        if(area != (maxX - minX) * (maxY - minY)) return false;

        // check all points state
        for(Integer x: map.keySet()) {
            for(Integer y: map.get(x).keySet()) {
                int state = map.get(x).get(y);
                // boundary, internal
                if(x == minX || x == maxX) {
                    if(y == minY || y == maxY) {
                        // four vetex
                        if(state != 1 && state != 2 && state != 4 && state != 8) return false;
                    } else {
                        if(state != 5 && state != 10) return false;
                    }
                } else if(y == minY || y == maxY) {
                    if(state != 12 && state != 3) return false;
                } else {
                    if(state != 3 && state != 12 && state != 5 && state != 10 && state != 15) return false;
                }
            }
        }
        return true;
    }

    public boolean setBit(int x, int y, int bit) {
        if(!map.containsKey(x)) map.put(x, new HashMap<Integer, Integer>());
        if(!map.get(x).containsKey(y)) map.get(x).put(y, 0);
        int state = map.get(x).get(y);
        // if already set, this means an overlap
        if((state & bit) != 0) return false;
        map.get(x).put(y, state | bit);
        return true;
    }

}