3047. Find the Largest Area of Square Inside Two Rectangles | 1602

 1class Solution:
 2    def largestSquareArea(
 3        self, bottomLeft: List[List[int]], topRight: List[List[int]]
 4    ) -> int:
 5        # it's okay to be O(N**2)!
 6
 7        def calculateSquareArea(rec0: List[List[int]], rec1: List[List[int]]) -> int:
 8            # see leetcode 223.
 9            # rec0 = [leftbottom, righttop] = [[1,1], [3,3]]
10            # rec1 = [leftbottom, righttop] = [[2,2], [4,4]]
11
12            maxleft = max(rec0[0][0], rec1[0][0])
13            minright = min(rec0[1][0], rec1[1][0])
14            maxbottom = max(rec0[0][1], rec1[0][1])
15            mintop = min(rec0[1][1], rec1[1][1])
16
17            if maxleft >= minright or maxbottom >= mintop:  # no overlap
18                return 0
19
20            # return square of the shorter overlap
21            return min(minright - maxleft, mintop - maxbottom) ** 2
22
23        n = len(bottomLeft)
24        max_area = 0
25        rectangles = []
26
27        for i in range(n):
28            rectangles.append([bottomLeft[i], topRight[i]])
29
30        # print(rectangles)
31
32        for i, rec0 in enumerate(rectangles[:-1]):
33            for rec1 in rectangles[i + 1 :]:
34                area = calculateSquareArea(rec0, rec1)
35                # print(rec0, rec1, area)
36                if area > max_area:
37                    max_area = area
38
39        return max_area