Python solution with detailed explanations


  • 0
    G

    Solution

    Perfect Rectangle https://leetcode.com/problems/perfect-rectangle/

    Linear Time Algorithm

    • Two conditions need to be satisfied to have a perfect rectangle cover
    • Area of perfect rectangle is sum of area of unit rectangles
    • Say we identify all four points as a tuple of every unit rectangle. Now say we add the 4 points for every rectangle to a map. This gives us a frequency distribution of each possible point. The insight is that if these rectangles form a perfect rectangle, then the outer four points of this perfect rectangle will each have a frequency of 1. All other points will have a frequency of either 2 or 4.
    from collections import defaultdict
    from pprint import pprint
    
    class Solution(object):
        def area(self, r):
            return abs((r[0]-r[2])*(r[1]-r[3]))
    
        def build_r_map(self, rectangles):
            total_area, pt = 0, defaultdict(int)
            for r in rectangles:
                total_area += self.area(r)
                pt[(r[0],r[1])], pt[(r[2],r[3])] = pt[(r[0],r[1])]+1, pt[(r[2],r[3])]+1
                pt[(r[2],r[1])], pt[(r[0],r[3])] = pt[(r[2],r[1])]+1, pt[(r[0],r[3])]+1            
            return total_area, pt
    
        def test_and_get_cover(self, pt, outer):
            for k,v in pt.items():
                if v == 1:
                    if len(outer) >= 4:
                        return False
                    outer[k[0]].append(k)
                elif v % 2 != 0 or v > 4:
                    return False
            return True
    
        def isRectangleCover(self, rectangles):
            """
            :type rectangles: List[List[int]]
            :rtype: bool
            """
            # build_r_map will return a dictionary pt which is a frequency map of all possible points.
            total_area, pt = self.build_r_map(rectangles)
            outer = defaultdict(list)
            # test_and_get_cover will make sure each point has either frequency 1 or 2 or 4.
            # Points with frequency 1 will be put in a map with key as their x-coordinate.
            if self.test_and_get_cover(pt, outer):
                # Sorting the keys helps us get the left and right sides of the rectangle
                k = sorted(outer.keys())
                # Test that there are 4 points in all which can split into 2 pairs such that both pairs have same x co-ordinate
                if len(k) == 2 and len(outer[k[0]]) == 2 and len(outer[k[1]]) == 2:
                    # Since we sorted x co-ordinate, we know left and right side. This helps in figuring the bottom left and top right points
                    bl, tr = min(outer[k[0]], key=lambda x:x[1]), max(outer[k[1]], key=lambda x:x[1])
                    # test the final condition for total area.
                    if total_area == self.area([bl[0], bl[1], tr[0], tr[1]]):
                        return True
            return False
    

Log in to reply
 

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