Easy Understanding O(n) Python Solution


  • 10

    Save area and all FOUR corners for each sub-rectangle:

    1. sum of area of all sub-rectangle == area of maximum rectangle.
    2. each corner should only appear either TWO or FOUR times, except four corners of big rectangle.
    class Solution(object):
        def isRectangleCover(self, rectangles):
            def recordCorner(point):
                if point in corners:
                    corners[point] += 1
                else:
                    corners[point] = 1
    
            corners = {}                                # record all corners 
            L, B, R, T, area = float('inf'), float('inf'), -float('inf'), -float('inf'), 0
    
            for sub in rectangles:
                L, B, R, T = min(L, sub[0]), min(B, sub[1]), max(R, sub[2]), max(T, sub[3])
                ax, ay, bx, by = sub[:]
                area += (bx-ax)*(by-ay)                 # sum up the area of each sub-rectangle
                map(recordCorner, [(ax, ay), (bx, by), (ax, by), (bx, ay)])
    
            if area != (T-B)*(R-L): return False        # check the area
    
            big_four = [(L,B),(R,T),(L,T),(R,B)]
    
            for bf in big_four:                         # check corners of big rectangle
                if bf not in corners or corners[bf] != 1:
                    return False
    
            for key in corners:                         # check existing "inner" points
                if corners[key]%2 and key not in big_four:
                    return False
    
            return True
    

  • 0
    L

    Does the answer can handle the example [[0, 0, 1, 2], [1, 0, 2, 1], [1, 0, 2, 1], [2, 0, 3, 2]]?


  • 0

    @lhq In this case: [[0, 0, 1, 2], [1, 0, 2, 1], [1, 0, 2, 1], [2, 0, 3, 2]], (1, 0) and (2, 1) actually appears 3 times because all four corners of sub-rectangle needs to be recorded.


  • 0
    L

    @YJL1228 I got it, thanks.


  • 0
    M

    what about [(0,0,1,1), (0,1,3,2), (1,0, 2,2), (3,0, 4,2)]


Log in to reply
 

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