# Python solution with detailed explanations

• 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

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

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