PYTHON || Runtime 393 ms Beats 99.97% of users with Python3
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem involves finding the largest square area formed by rectangles defined by th
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem involves finding the largest square area formed by rectangles defined by their bottom-left and top-right coordinates. The intuition behind this approach is to sort the rectangles based on their bottom-left x-coordinate. By doing this, we can efficiently iterate through the rectangles and consider them in a sorted order, optimizing the process of finding the largest square area.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSort the rectangles based on their bottom-left x-coordinate.\nIterate through the sorted rectangles:\nFor each rectangle at index r, find the minimum side length of the square that can be formed by rectangles from index l to r.\nUpdate the result if a larger square area is found.\nMove the left index l to the right, ensuring that it doesn\'t exceed the current rectangle\'s x-coordinate.\nReturn the square of the maximum area found.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(nlogn), where n is the number of rectangles. The sorting step dominates the time complexity.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n), where n is the number of rectangles. The space is used to store the sorted order.\n\n# Code\n```\nclass Solution:\n    def largestSquareArea(self, bottomLeft: List[List[int]], topRight: List[List[int]]) -> int:\n        def best(i, j):\n            return min(max(min(topRight[i][d], topRight[j][d]) - max(bottomLeft[i][d], bottomLeft[j][d]), 0) for d in range(2))\n\n        n = len(bottomLeft)\n        order = sorted(range(n), key=lambda i: (bottomLeft[i][0], topRight[i][0]))\n        l, res = 0, 0\n        for r in range(n):\n            if min(topRight[order[r]][d] - bottomLeft[order[r]][d] for d in range(2)) <= res:\n                continue\n            while l < r and topRight[order[l]][0] <= bottomLeft[order[r]][0]:\n               l += 1\n            for l2 in range(l, r):\n                res = max(res, best(order[l2], order[r]))\n        return res ** 2\n```
['Array', 'Math', 'Depth-First Search', 'Geometry', 'Sorting', 'Python', 'Python3']