# O(N) solution of Problem 3 based on range addition

• Update: This code fails the test case [[0, 1, 2, 3],[0, 1, 1, 2],[2, 2, 3, 3],[1, 0, 3, 1],[2, 0, 3, 1]]. Because this test case has overlap but still has the right height and width sum. Anyone can provide a right solution? I am wondering if this problem can be solved in O(N) time.

The basic idea is:

If the rectangles can cover a big rectangle [x0, y0, x1, y1], then for any x in [x0, x1], the total height of small rectangles should be y1 - y0; for any y in [y0, y1], the total width of small rectangles should be x1 - x0.

Based on this idea, we can firstly convert rectangles to ranges [begin, end, height] on x axis. Then we do a range addition on all these ranges. If they can form a large rectangle, the result should be a single range with height y1 - y0. Similarly, we can convert rectangles to ranges [begin, end, width] on y axis. Again, we check if the result is a single range whose width is x1 - x0.

``````public class Solution {

public boolean isRectangleCover(int[][] rectangles) {
Map<Integer, Integer> x = new HashMap<>();
Map<Integer, Integer> y = new HashMap<>();
int xMin = Integer.MAX_VALUE, xMax = Integer.MIN_VALUE;
int yMin = Integer.MAX_VALUE, yMax = Integer.MIN_VALUE;
for(int[] rect: rectangles) {
int width = rect[2] - rect[0];
int height = rect[3] - rect[1];
increase(x, rect[0], height);
increase(x, rect[2], -height);
increase(y, rect[1], width);
increase(y, rect[3], -width);
xMin = Math.min(xMin, rect[0]);
xMax = Math.max(xMax, rect[2]);
yMin = Math.min(yMin, rect[1]);
yMax = Math.max(yMax, rect[3]);
}
int xCount = 0, yCount = 0, height = 0, width = 0;
for(int val: x.values()) {
if(val != 0) {
xCount ++;
height = Math.abs(val);
}
}
for(int val: y.values()) {
if(val != 0) {
yCount ++;
width = Math.abs(val);
}
}
return xCount == 2 && yCount == 2 && height == yMax-yMin && width == xMax-xMin;
}

private void increase(Map<Integer, Integer> map, int key, int inc) {
map.put(key, map.containsKey(key)? (map.get(key)+inc): inc);
}
}
``````