# A (hopefully) correct solution to the Perfect Rectangle problem

• This one cost me 10 minutes of penalty time because of a very stupid typo in `getBounds`, but otherwise it passes all OJ tests, and this tricky test too:

`[[0, 1, 2, 3],[0, 1, 1, 2],[2, 2, 3, 3],[1, 0, 3, 1],[2, 0, 3, 1]]`

The idea is to compare the total area first. If it doesn't match, return `false`, otherwise check for overlaps.

To check for overlaps, I sweep through the area along a certain axis (I chose `x`, a more efficient algorithm would pick one for a reason). While sweeping, check for overlaps with other rectangles along the other axis. Once an overlap is found, return `false` immediately.

To sweep, I build a list of “key points”. These are coordinates where a rectangle starts or ends. I sort them so ends come before starts, so where rectangles touch, I always remove ending ones first, therefore I don't have to do any special checks for overlaps at rectangle borders (which are fine).

To check for overlaps, I use the same key point structure, but this time I perform a binary search to figure out where to put the next rectangle. It must go either before/after all others, or between end of one rectangle and start of another, otherwise we have an overlap.

The complexity is probably awful. A loop over key points is `O(n)` already, where `n` is the number of rectangles. Then there is these insert/remove, which are `O(n)` as well, which gives the worst-case complexity of `O(n^2)`, I think. But insert/remove are actually tremendously fast on modern hardware, so it passes the OJ. A funny thing is that if I don't do that binary search in the `remove` function, but just call `remove(<key point>)`, which is also `O(n)`, then I get TLE because `ArrayList` compares every element to the one being removed. Removing by index, on the other hand, is probably just a `memcpy` call.

One way to optimize this would be to use an interval tree instead of a list, but that would certainly take a lot of time to code. Even this code was much uglier when I first submitted it during the contest. This is the result of cleaning it up a bit:

``````    public boolean isRectangleCover(int[][] rectangles) {
int totalArea = Stream.of(rectangles).mapToInt(r -> area(r)).sum();
if (totalArea != area(getBounds(rectangles)))
return false;
List<KeyPoint> keyPointsX = new ArrayList<>();
for (int i = 0; i < rectangles.length; ++i) {
}
Collections.sort(keyPointsX);
KeyPointList keyPointsY = new KeyPointList();
for (KeyPoint kpx : keyPointsX) {
KeyPoint start = new KeyPoint(kpx.rectangle[1], kpx.rectangle, false);
KeyPoint end = new KeyPoint(kpx.rectangle[3], kpx.rectangle, false);
if (kpx.isRectangleEndsHere()) {
keyPointsY.remove(start);
keyPointsY.remove(end);
} else {
int insertionPoint = keyPointsY.getNonOverlappingInsertionPoint(start, end);
if (insertionPoint == -1)
return false;
}
}
return true;
}

private int[] getBounds(int[][] rectangles) {
int[] bounds = new int[4];
int left = Integer.MAX_VALUE, right = Integer.MIN_VALUE,
top = Integer.MIN_VALUE, bottom = Integer.MAX_VALUE;
for (int i = 0; i < rectangles.length; ++i) {
left = Math.min(left, rectangles[i][0]);
right = Math.max(right, rectangles[i][2]);
top = Math.max(top, rectangles[i][3]);
bottom = Math.min(bottom, rectangles[i][1]);
}
bounds[0] = left;
bounds[1] = bottom;
bounds[2] = right;
bounds[3] = top;
return bounds;
}

private static int area(int[] rectangle) {
return (rectangle[2] - rectangle[0]) * (rectangle[3] - rectangle[1]);
}

private static class KeyPointList {
final List<KeyPoint> keyPoints = new ArrayList<>();

void remove(KeyPoint keyPoint) {
keyPoints.remove(Collections.binarySearch(keyPoints, keyPoint));
}

int getNonOverlappingInsertionPoint(KeyPoint start, KeyPoint end) {
int startIndex = -Collections.binarySearch(keyPoints, start) - 1;
int endIndex = -Collections.binarySearch(keyPoints, end) - 1;
if (overlaps(startIndex, endIndex))
return -1;
return startIndex;
}

private boolean overlaps(int startIndex, int endIndex) {
if (startIndex != endIndex)
return true; // some rectangle start or ends inside this one
if (startIndex == 0)
return false; // this one comes before the first starts
KeyPoint preceding = keyPoints.get(startIndex - 1);
if (preceding.isRectangleStartsHere())
return true; // this one is completely inside another rectangle
return false;
}

void add(int insertionPoint, KeyPoint start, KeyPoint end) {
}
}

private static class KeyPoint implements Comparable<KeyPoint> {
final int coordinate;
final int[] rectangle;
private final boolean horizontal;

KeyPoint(int coordinate, int[] rectangle, boolean horizontal) {
this.coordinate = coordinate;
this.rectangle = rectangle;
this.horizontal = horizontal;
}

boolean isRectangleStartsHere() {
return horizontal
? coordinate == rectangle[0]
: coordinate == rectangle[1];
}

boolean isRectangleEndsHere() {
return horizontal
? coordinate == rectangle[2]
: coordinate == rectangle[3];
}

@Override
public int compareTo(KeyPoint o) {
int xc = Integer.compare(coordinate, o.coordinate);
if (xc == 0) {
if (isRectangleEndsHere() && o.isRectangleStartsHere())
return -1;
else if (isRectangleStartsHere() && o.isRectangleEndsHere())
return +1;
else
return xc;
} else {
return xc;
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.