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-r)*(r-r)) def build_r_map(self, rectangles): total_area, pt = 0, defaultdict(int) for r in rectangles: total_area += self.area(r) pt[(r,r)], pt[(r,r)] = pt[(r,r)]+1, pt[(r,r)]+1 pt[(r,r)], pt[(r,r)] = pt[(r,r)]+1, pt[(r,r)]+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].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]) == 2 and len(outer[k]) == 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], key=lambda x:x), max(outer[k], key=lambda x:x) # test the final condition for total area. if total_area == self.area([bl, bl, tr, tr]): return True return False