Simple Python O(n) Solution by cancelling corners, Explained


  • 2
    A

    The idea is simple:
    there are 4 types of corners: 0: '┗', 1: '┏', 2: '┛', and 3: '┓'.
    At the same point, corner 0 will cancel corner 1 or 2. Similarly, 1 will cancel 0 or 3, 2 will cancel 0 or 3, 3 will cancel 1 or 2.
    And for all the given rectangles to form an exact cover of a rectangular region, all corners should be cancelled except for the 4 corners of the rectangular region.
    We can use a Set to keep track of the corners: for each rectangle we are given, we check all its 4 corners (4 types), if they can cancel a corner in the set, then cancel that corner; else we put them in the set. At the end, we should have a set with the only 4 corners of the rectangular region in it, otherwise we return False.

        def isRectangleCover(self, rectangles):
            """
            :type rectangles: List[List[int]]
            :rtype: bool
            """
            points = set()
            min_x, min_y, max_x, max_y = rectangles[0]
            cancel = [(1, 2), (0, 3), (0, 3), (1, 2)]
    
            for x1, y1, x2, y2 in rectangles:
                for x, y, d in [(x1, y1, 0), (x1, y2, 1), (x2, y1, 2), (x2, y2, 3)]:
                    if (x, y, d) in points:  # there should be no same type of corner at the same point
                            return False
                    c1, c2 = cancel[d]
                    if (x, y, c1) in points:
                        points.remove((x, y, c1))
                        continue
                    elif (x, y, c2) in points:
                        points.remove((x, y, c2))
                        continue
                    else:
                        points.add((x, y, d))
    
                min_x, min_y, max_x, max_y = min(min_x, x1), min(min_y, y1), max(max_x, x2), max(max_y, y2)
    
            return points == {(min_x, min_y, 0), (min_x, max_y, 1), (max_x, min_y, 2), (max_x, max_y, 3)}
    

Log in to reply
 

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