391.Perfect Rectangle

Tags: [knowledge], [math], [map], [trick], [override_hash], [override_eq]

Com: {g}

Link: https://leetcode.com/problems/perfect-rectangle/#/description

Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.

Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Example 1:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [3,2,4,4],
  [1,3,2,4],
  [2,3,3,4]
]

Return true. All 5 rectangles together form an exact cover of a rectangular region.

Example 2:

rectangles = [
  [1,1,2,3],
  [1,3,2,4],
  [3,1,4,2],
  [3,2,4,4]
]

Return false. Because there is a gap between the two rectangular regions.

Example 3:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [3,2,4,4]
]

Return false. Because there is a gap in the top center.

Example 4:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [2,2,4,4]
]

Return false. Because two of the rectangles overlap with each other.

Solution: Knowledge, Map

class Solution(object):

    class Point(object):
        def __init__(self, x, y):
            self.x = x
            self.y = y

        def __hash__(self):
            return hash((self.x, self.y))

        def __eq__(self, other):
            return isinstance(other, self.__class__) and\
                   self.x == other.x and\
                   self.y == other.y


    def isRectangleCover(self, rectangles):
        """
        :type rectangles: List[List[int]]
        :rtype: bool
        """
        if not rectangles:
            return False

        min_x = sys.maxint
        min_y = sys.maxint
        max_x = -1
        max_y = -1
        areas_sum = 0

        points = collections.defaultdict(lambda: 0)
        for rect in rectangles:
            BL = self.Point(rect[0], rect[1])
            TR = self.Point(rect[2], rect[3])
            BR = self.Point(TR.x, BL.y)
            TL = self.Point(BL.x, TR.y)

            area = (BR.x - BL.x) * (TR.y - BR.y)
            areas_sum += area

            min_x = min(min_x, BL.x, TR.x, BR.x, TL.x)
            min_y = min(min_y, BL.y, TR.y, BR.y, TL.y)
            max_x = max(max_x, BL.x, TR.x, BR.x, TL.x)
            max_y = max(max_y, BL.y, TR.y, BR.y, TL.y)

            points[BL] += 1
            points[TR] += 1
            points[BR] += 1
            points[TL] += 1

        main_BL = self.Point(min_x, min_y)
        main_TR = self.Point(max_x, max_y)
        main_BR = self.Point(main_TR.x, main_BL.y)
        main_TL = self.Point(main_BL.x, main_TR.y)

        total_area = (main_BR.x - main_BL.x) * (main_TR.y - main_BR.y)
        if areas_sum != total_area:
            return False

        for point in points:
            if point in (main_BL, main_TR, main_BR, main_TL) and points[point] != 1:
                return False

            if point not in (main_BL, main_TR, main_BR, main_TL) and points[point] % 2 == 1:
                return False

        return True

Revelation:

• If the given rectangles can be formed as a perfect rectangle, it need satisfy 3 conditions:
• (1) The main area should be equal to the sum of areas of all rectangles.
• (2) The four corner points (main_BL, main_TR, main_BR, main_TL) should only appear one time, which guarantees there is no overlapping.
• (3) Other points should appear either 2 or 4 times, which guarantees there is no overlapping and there is no spaces.

Note:

• Time complexity = O(n), n is the number of rectangles.
• Space complexity = O(4*n) = O(n), n is the number of rectangles.