Clean O(n) Python solution


  • 0

    Python code of this algorithm.

    class Solution(object):
        def isRectangleCover(self, rectangles):
            
            def update_counts(x, y, bit):
                mask, nums = counts[x, y]
                if mask & bit: 
                    return False
                counts[x, y] = [mask | bit, nums + 1]
                return True
            
            counts, area = collections.defaultdict(lambda: [0, 0]), 0
            minx, maxx, miny, maxy = float('inf'), float('-inf'), float('inf'), float('-inf')
            
            for blx, bly, trx, _try in rectangles:
                tlx, tly = blx, _try
                brx, bry = trx, bly
                minx, miny, maxx, maxy = min(minx, blx), min(miny, bly), max(maxx, trx), max(maxy, _try)
                if not update_counts(tlx, tly, 1):  return False
                if not update_counts(trx, _try, 2): return False
                if not update_counts(blx, bly, 4):  return False
                if not update_counts(brx, bry, 8):  return False
                area += (trx - blx) * (_try - bly)
                
            if area != (maxx - minx) * (maxy - miny): return False
                
            for x, y in counts:
                nums = counts[x, y][1]
                if (x == minx or x == maxx) and (y == miny or y == maxy):
                    if nums != 1: 
                        return False
                else:
                    if nums != 2 and nums != 4:
                        return False
            
            return True```

Log in to reply
 

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