[Python3] Rectangles intersections || description with images
The solution bases on the similar problem 223. Rectangle Area\n\n\n\n### Algorithm (for solution with sorting optimization)\n1. Group all rectangle coordinats u
##### The solution bases on the similar problem [223. Rectangle Area](https://leetcode.com/problems/rectangle-area/description/)\n![image.png](https://assets.leetcode.com/users/images/2aee39ea-67a9-4163-acc7-97e9379542e7_1708842827.9125948.png)\n![image.png](https://assets.leetcode.com/users/images/1ebbb1fe-95d0-4198-b8e5-7a4c5c5cf173_1708842904.4121776.png)\n![image.png](https://assets.leetcode.com/users/images/d11b9e94-afb3-4b8b-94c6-2eadcb9b044f_1708842891.7676077.png)\n### Algorithm (for solution with sorting optimization)\n1. Group all rectangle coordinats using `zip` and `sort`, it will help to optimize finding intersections in the future. Of course you can skipp sorting, but will be needed to check all possible intersections of rectangles in the future (remove the line `if overlapX < 0 and overlapY < 0: break `).\n1. We are given four points - `ax1,ay1,ax2,ay2` and `bx1,by1,bx2,by2`\n\n1. Calculate the overlap by the `X asis` :\n`overlapX = min(ax2, bx2) \u2212 max(ax1, bx1)`\n\n1. Calculate the overlap by the `Y asis` :\n`overlapY = min(ay2, by2) - max(ay1, by1)`\n\n1. If both `overlapX` and `overlapY` are negative it means no more intersactions between `i-th` rectangle and any other unprocessed `j-th` rectangle. Just move to the next `i-th` rectangle: `if overlapX < 0 and overlapY < 0: break `. If you didn\'t sort the coordinats, this optimization line of code don\'t needed.\n\n1. If both `overlapX` and `overlapY` are positive, find the maximum possible square, what exists in this overlapping area. It can be easy made by finding a minimum side `min(overlapX, overlapY)`, because all sides in rectangle are equals.\n\n1. Save to the `res` variable maximum possible side of the final square\n\n1. After processing all pairs we need return the maximum square area, what equal to `side * side` => `return res * res`\n\n#### The below two examples of code:\n###### The final speed depends on input data. If we have a lot of rectangles and not big intersection groups, then sorting is more profitable, because we will skip a lot of not needed comparisons between rectangles. Otherwise, if intersections groups are large in comparison with a count of rectangles (imagine almost all rectangles have intersections), than the second approach, without sorting, will be more profitable.\n#### With sorting:\n```python3 []\nclass Solution:\n    def largestSquareArea(self, bottomLeft: List[List[int]], topRight: List[List[int]]) -> int:\n        res = 0 # the rectange side\n        # [[(ax1, ay1), (ax2, ay2)], [(bx1, by1), (bx2, by2)]]\n        coordinats = sorted(zip(bottomLeft, topRight))\n\n        for i in range(len(coordinats)):\n            for j in range(i + 1, len(coordinats)):\n                ax1, ay1 = coordinats[i][0]\n                ax2, ay2 = coordinats[i][1]\n                bx1, by1 = coordinats[j][0]\n                bx2, by2 = coordinats[j][1]\n\n                overlapX = min(ax2, bx2) - max(ax1, bx1)\n                overlapY = min(ay2, by2) - max(ay1, by1)\n\n                # move to the next i-th rectangle, no more intersactions between i-th and j-th rectangles\n                if overlapX < 0 and overlapY < 0: break \n                if overlapX > 0 and overlapY > 0:\n                    minSquareSide = min(overlapX, overlapY)\n                    res = max(res, minSquareSide)\n\n        return res * res\n```\n#### Without sorting optimization:\n```python3 []\nclass Solution:\n    def largestSquareArea(self, bottomLeft: List[List[int]], topRight: List[List[int]]) -> int:\n        res = 0 # the rectange side\n        coordinats = list(zip(bottomLeft, topRight))\n        \n        for ((ax1, ay1), (ax2, ay2)), ((bx1, by1), (bx2, by2)) in combinations(coordinats, 2):\n            overlapX = min(ax2, bx2) - max(ax1, bx1)\n            overlapY = min(ay2, by2) - max(ay1, by1)\n\n            if overlapX > 0 and overlapY > 0:\n                minSquareSide = min(overlapX, overlapY)\n                res = max(res, minSquareSide)\n\n        return res * res\n```\n\n#### More geometry problems to practise:\n[836. Rectangle Overlap (E)](https://leetcode.com/problems/rectangle-overlap/description/)\n[223.Rectangle-Area (M)](https://leetcode.com/problems/rectangle-area/description/)\n[335.Self-Crossing (H)](https://leetcode.com/problems/self-crossing/description/)\n[391.Perfect-Rectangle (H)](https://leetcode.com/problems/perfect-rectangle/description/)\n[587.Erect-the-Fence\xA0(H)](https://leetcode.com/problems/erect-the-fence/description/)\n[593.Valid-Square\xA0(H)](https://leetcode.com/problems/valid-square/description/)\n[858.Mirror-Reflection\xA0(H)](https://leetcode.com/problems/mirror-reflection/description/)\n[1401.Circle-and-Rectangle-Overlapping\xA0(M)](https://leetcode.com/problems/circle-and-rectangle-overlapping/description/)\n[1453.Maximum-Number-of-Darts-Inside-of-a-Circular-Dartboard\xA0(H)](https://leetcode.com/problems/maximum-number-of-darts-inside-of-a-circular-dartboard/description/)\n[1610.Maximum-Number-of-Visible-Points\xA0(H)](https://leetcode.com/problems/maximum-number-of-visible-points/description/)\n[2280.Minimum-Lines-to-Represent-a-Line-Chart\xA0(M)](https://leetcode.com/problems/minimum-lines-to-represent-a-line-chart/description/)\n
['Math', 'Geometry', 'Python', 'Python3']