Sweepline Algorithm Python
\n# Approach\nUse a sweepline algorithm by adding events of rectangles startx and endx.\nCheck all rectangles it intersects on the x plane and check if they int
\n# Approach\nUse a sweepline algorithm by adding events of rectangles startx and endx.\nCheck all rectangles it intersects on the x plane and check if they intersect on y plane. If they do calculate the intersection points and find the minSide.\n\n# Complexity\n- Time complexity:\nO(n^2) at worse\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def largestSquareArea(self, bottomLeft: List[List[int]], topRight: List[List[int]]) -> int:\n        events = []\n        for i, (bl, tr) in enumerate(zip(bottomLeft, topRight)):\n            events.append((bl[0], \'start\', i))\n            events.append((tr[0], \'end\', i))\n        \n        events.sort()  # Sort by x-coordinate, then by \'start\' before \'end\'\n\n        def getIntersection(a, b):\n            # Find intersection of two rectangles, a and b\n            bl1, tr1 = bottomLeft[a], topRight[a]\n            bl2, tr2 = bottomLeft[b], topRight[b]\n            intersect_bl = (max(bl1[0], bl2[0]), max(bl1[1], bl2[1]))\n            intersect_tr = (min(tr1[0], tr2[0]), min(tr1[1], tr2[1]))\n            if intersect_bl[0] < intersect_tr[0] and intersect_bl[1] < intersect_tr[1]: \n                return intersect_bl, intersect_tr\n            return None\n\n        maxSquareArea = 0\n        active = set()\n\n        for x, event, i in events:\n            if event == \'start\':\n                for j in active:\n                    intersection = getIntersection(i, j)\n                    if intersection:\n                        bl, tr = intersection\n                        side = min(tr[0] - bl[0], tr[1] - bl[1])\n                        maxSquareArea = max(maxSquareArea, side ** 2)\n                active.add(i)\n            else:\n                active.remove(i)\n\n        return maxSquareArea\n\n```
['Python3']