# Java Use Sort (O(nlogn) time complexity) with Detailed Explanation

The rough idea includes two steps:

1. Check Overlapping of all rectangles, if overlapping, `return false`
2. no overlapping, find the `bottom-left point`t and `up-right point` of the possible biggest merged rectangle. We can calculate its `area`.
if `area == sum(all input rectangles' area)`, return `true`. Or `false`.

Let's to explain the first step, How to check overlapping?
We need to check `x-axis` and `y-axis` separately.
For `x-aixs`:
sort the input in `ascending` order according to the `left-line` of rectangle. Then if `current rectangle's left line < pre-rectangles' right line` && `((current rectangle's up-line < pre-rectangles' up-line && current rectangle's up-line > pre-rectangles' bottom-line) || (current rectangle's bottom-line < pre-rectangles' up-line && current rectangle's bottom-line > pre-rectangles' bottom-line))`(this condition checks the situation that current rectangle on top of previous one or below bottom of previous one), it means current rectangle `overlaps`previous one.

For `y-axis', it's the same as`x-axis`:

sort the input in `ascending` order according to the `bottom-line` of rectangle. Then if `current rectangle's bottom line < pre-rectangles' up line` && `((current rectangle's left-line < pre-rectangles' right-line && current rectangle's left-line > pre-rectangles' left-line) || (current rectangle's right-line < pre-rectangles' right-line && current rectangle's right-line > pre-rectangles' left-line))`(this condition checks the situation that current rectangle on left of previous one or on right of previous one), it means current rectangle `overlaps` previous one.

The second Step:
Most important thing is to find left-bottom point and up-right point.
We need to find four points at first:
left-most, bottom-most, right-most, up-most
The `left-most` and `bottom-most` must be the same point, and The `right-most` and `up-most` must be the same point. If not, it can not be a perfect rectangle.

``````public boolean isRectangleCover(int[][] rectangles) {
if (rectangles == null || rectangles.length == 0) {
return false;
}
int n = rectangles.length;
List<int[]> list = new ArrayList<>();
for (int[] rec: rectangles) {
}
Collections.sort(list, new Comparator<int[]>() { // sort list to check x-axis
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
for (int i = 1; i < list.size(); i++) {
int[] pre = list.get(i - 1);
int[] cur = list.get(i);
if (cur[0] < pre[2] && ((cur[1] < pre[3] && cur[1] > pre[1]) || (cur[3] < pre[3] && cur[3] > pre[1]))) { // overlap
return false;
}
}
Collections.sort(list, new Comparator<int[]>() { // sort list to check y-axis
@Override
public int compare(int[] o1, int[] o2) {
return o1[1] - o2[1];
}
});
long area = 0;
int[] leftPoint = {Integer.MAX_VALUE, Integer.MAX_VALUE};
int[] bottomPoint = {Integer.MAX_VALUE, Integer.MAX_VALUE};
int[] rightPoint = {Integer.MIN_VALUE, Integer.MIN_VALUE};
int[] upPoint = {Integer.MIN_VALUE, Integer.MIN_VALUE};

int[] pre = new int[4];
for (int i = 0; i < list.size(); i++) { // we find four points when we check overlapping
int[] cur = list.get(i);
if (i > 0 && cur[1] < pre[3] && ((cur[0] < pre[2] && cur[0] > pre[0]) || (cur[2] < pre[2] && cur[2] > pre[0]))) { // overlap
return false;
}
int[] rec = cur;
if (rec[0] < leftPoint[0] || (rec[0] == leftPoint[0] && rec[1] < leftPoint[1])) {
leftPoint = new int[] {rec[0], rec[1]};
}
if (rec[1] < bottomPoint[1] || (rec[1] == bottomPoint[1] && rec[0] < bottomPoint[0])) {
bottomPoint = new int[] {rec[0], rec[1]};
}
if (rec[2] > rightPoint[0] || (rec[2] == rightPoint[0] && rec[3] > rightPoint[1])) {

rightPoint = new int[] {rec[2], rec[3]};
}
if (rec[3] > upPoint[1] || (rec[3] == upPoint[1] && rec[2] > upPoint[0])) {
upPoint = new int[] {rec[2], rec[3]};
}
area += (rec[3] - rec[1]) * (rec[2] - rec[0]);
pre = cur;
}

if (leftPoint[0] != bottomPoint[0] || leftPoint[1] != bottomPoint[1] || rightPoint[0] != upPoint[0] || rightPoint[1] != upPoint[1]) {
//check left point == bottom point && up point == right point
return false;
}

// check area
return area == (long) (rightPoint[1] - leftPoint[1]) * (long) (rightPoint[0] - leftPoint[0]);
}
``````

• Modify a little error in check overlapping: (missing some "=")
For x-aixs:
sort the input in ascending order according to the left-line of rectangle. Then if current rectangle's left line < pre-rectangles' right line && ((current rectangle's up-line <= pre-rectangles' up-line && current rectangle's up-line > pre-rectangles' bottom-line) || (current rectangle's bottom-line < pre-rectangles' up-line && current rectangle's bottom-line >= pre-rectangles' bottom-line))(this condition checks the situation that current rectangle on top of previous one or below bottom of previous one), it means current rectangle overlapsprevious one.

For y-axis', it's the same asx-axis`:

sort the input in ascending order according to the bottom-line of rectangle. Then if current rectangle's bottom line < pre-rectangles' up line && ((current rectangle's left-line < pre-rectangles' right-line && current rectangle's left-line >= pre-rectangles' left-line) || (current rectangle's right-line <= pre-rectangles' right-line && current rectangle's right-line > pre-rectangles' left-line))(this condition checks the situation that current rectangle on left of previous one or on right of previous one), it means current rectangle overlaps previous one.

``````    public boolean isRectangleCover(int[][] rectangles) {
if (rectangles == null || rectangles.length == 0) {
return false;
}
int n = rectangles.length;
List<int[]> list = new ArrayList<>();
for (int[] rec: rectangles) {
}
Collections.sort(list, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
for (int i = 1; i < list.size(); i++) {
int[] pre = list.get(i - 1);
int[] cur = list.get(i);
if (cur[0] < pre[2] && ((cur[1] < pre[3] && cur[1] >= pre[1]) || (cur[3] <= pre[3] && cur[3] > pre[1]))) {
return false;
}
}
Collections.sort(list, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1] - o2[1];
}
});
long area = 0;
int[] leftPoint = {Integer.MAX_VALUE, Integer.MAX_VALUE};
int[] bottomPoint = {Integer.MAX_VALUE, Integer.MAX_VALUE};
int[] rightPoint = {Integer.MIN_VALUE, Integer.MIN_VALUE};
int[] upPoint = {Integer.MIN_VALUE, Integer.MIN_VALUE};

int[] pre = new int[4];
for (int i = 0; i < list.size(); i++) {
int[] cur = list.get(i);
if (i > 0 && cur[1] < pre[3] && ((cur[0] < pre[2] && cur[0] >= pre[0]) || (cur[2] <= pre[2] && cur[2] > pre[0]))) {
return false;
}
int[] rec = cur;
if (rec[0] < leftPoint[0] || (rec[0] == leftPoint[0] && rec[1] < leftPoint[1])) {
leftPoint = new int[] {rec[0], rec[1]};
}
if (rec[1] < bottomPoint[1] || (rec[1] == bottomPoint[1] && rec[0] < bottomPoint[0])) {
bottomPoint = new int[] {rec[0], rec[1]};
}
if (rec[2] > rightPoint[0] || (rec[2] == rightPoint[0] && rec[3] > rightPoint[1])) {

rightPoint = new int[] {rec[2], rec[3]};
}
if (rec[3] > upPoint[1] || (rec[3] == upPoint[1] && rec[2] > upPoint[0])) {
upPoint = new int[] {rec[2], rec[3]};
}
area += (rec[3] - rec[1]) * (rec[2] - rec[0]);
pre = cur;
}

if (leftPoint[0] != bottomPoint[0] || leftPoint[1] != bottomPoint[1] || rightPoint[0] != upPoint[0] || rightPoint[1] != upPoint[1]) {
return false;
}

return area == (long) (rightPoint[1] - leftPoint[1]) * (long) (rightPoint[0] - leftPoint[0]);
}
``````

• The overlapping check still has some problem.
Can't pass test case like [[1,1,3,3],[2,2,4,4],[4,1,5,4],[1,3,2,4]].
The overlapping check will ignore those overlaps if the overlapping rectangles are not next to each other after sort. And once size of the overlapping area math the size of missing area we will get a wrong answer.

• [[1,1,3,3],[2,2,4,4],[4,1,5,4],[1,3,2,4]]

Thanks! You are right. Any suggestions to solve that? It seems that we need check all the previous rectangles whose x-range include current rectangle's left line.

• @zhenh_leet
Agree. But check all those previous rectangles would be an n^2 solutions. Still trying to find a better solution.

• @zhenh_leet it looks like your solution assumes that if any two rectangles overlaps, then they must be adjacent in either x-axis ordered or y-axis ordered array. However, it seems not true.

• @zhenh_leet
we can check the overlap by check if width line overlap and height line overlap,

for example:
rec1(b1,l1,t1,r1)
rec2(b2,l2,t2,r2)
if (l1,r1) overlap (l2,r2) and (b1,t1) overlap (b2,t2), then rec1 overlap rec2

the following is python implementation of this method

``````   def checkJoint(self, rec1, rec2):
b1, l1, t1, r1 = rec1
b2, l2, t2, r2 = rec2
return ((b1 <= b2 and t1 > b2) or (b2 <= b1 and t2 > b1)) and ((l1 <= l2 and r1 > l2) or (l2 <= l1 and r2 > l1))
``````

I come up with the same idea as you to check overlap and sum of rectangle area, but checking overlap take O(n^2), it give a TLE

• @luffy_zc
Yes. It seems that this kind of checking will be O(n^2) which is not accepted. Another smart solution is counting the vertex.

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