Python3 rectangles, sorted left-to-right
Intuition\nSorting rectangles left-to-right improves average-case performance.\n\n# Approach\nCombine bottomLeft and topRight into a list of rects and\nsort the
# Intuition\nSorting rectangles left-to-right improves average-case performance.\n\n# Approach\nCombine `bottomLeft` and `topRight` into a list of `rects` and\nsort them from left to right. Use a standard i-j nested loop, but break out of the inner loop when the j-rectangle is too far to the right to improve the size of the square.\n\n# Complexity\n- Time complexity:\nWorst case $$O(n^2))$$, but often close to $$O(n log n)$$\n\n- Space complexity:\n$$O(N)$$\n\n# Code\n```\nclass Solution:\n \n    def largestSquareArea(self, bottomLeft: List[List[int]], topRight: List[List[int]]) -> int:\n\n        # Sort rectangles by their minimum x value to improve brute-force method.\n        rects = sorted((x0, y0, x1, y1) for (x0, y0), (x1, y1) in zip(bottomLeft, topRight))\n      \n        bestSide = 0\n        n = len(rects)\n        # Compare rects[i] with rects[j], where rects[i] < rects[j] from left-to-right.\n        for i in range(n - 1):\n            ix0, iy0, ix1, iy1 = rects[i]\n            for j in range(i + 1, n):\n                jx0, jy0, jx1, jy1 = rects[j]\n                # Break if the rects[j] is too far to the right to improve bestSide.\n                # This usually improves the average-case runtime.\n                if ix1 - jx0 <= bestSide:\n                    break\n                dx = min(ix1, jx1) - jx0\n                if dx <= bestSide:\n                    continue\n                dy = min(iy1, jy1) - max(iy0, jy0)\n                bestSide = max(bestSide, min(dx, dy))\n        return bestSide * bestSide\n        \n```
['Python3']