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


  • 0
    Z

    Hope it helpful!

    The rough idea includes two steps:

    1. Check Overlapping of all rectangles, if overlapping, return false
    2. no overlapping, find the bottom-left pointt 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 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.

    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) {
             list.add(rec);
         }
         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]);
     }
    

  • 0
    Z

    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) {
                list.add(rec);
            }
            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]);
        }
    

  • 0
    T

    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.


  • 0
    Z

    @tizzy said in Java Use Sort (O(nlogn) time complexity) with Detailed Explanation:

    [[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.


  • 0
    T

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


  • 0
    D

    @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.


  • 0
    L

    @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


  • 0
    Z

    @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.


Log in to reply
 

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