<p>You are given an array of points in the <strong>X-Y</strong> plane <code>points</code> where <code>points[i] = [x<sub>i</sub>, y<sub>i</sub>]</code>.</p>

<p>Return <em>the minimum area of a rectangle formed from these points, with sides parallel to the X and Y axes</em>. If there is not any such rectangle, return <code>0</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/03/rec1.JPG" style="width: 500px; height: 447px;" />
<pre>
<strong>Input:</strong> points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
<strong>Output:</strong> 4
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/03/rec2.JPG" style="width: 500px; height: 477px;" />
<pre>
<strong>Input:</strong> points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
<strong>Output:</strong> 2
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= points.length &lt;= 500</code></li>
	<li><code>points[i].length == 2</code></li>
	<li><code>0 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 4 * 10<sup>4</sup></code></li>
	<li>All the given points are <strong>unique</strong>.</li>
</ul>

class Solution1:
    def minAreaRect(self, points: List[List[int]]) -> int:
        """
        This is a simple N**2 solution where for each point, we look for other points that
        are in the opposite corner since it's easy to check if there's a rectangle because
        we know what other points we need.
        For example, consider the points:
        
        5
        4   c     d
        3
        2   a     b
        1  
        0 1 2 3 4 5

        If we pick a and d, we know what are the other 2 points needed to form a rectangle:
        (x of a, y of c) and (x of d, y of a).
        So if we have an index of points, we can check if they exist.
        """
        pointsSet = set()
        for point in points:
            pointsSet.add(tuple(point))

        minArea = math.inf
        while pointsSet:
            point = pointsSet.pop()
            for otherPoint in pointsSet:
                # This will cover 2 cases: the point is the same or the points have the same x or y.
                # Although,  the points are unique so it will just check that we don't go over points
                # that share 1 axis.
                if point[0] == otherPoint[0] or point[1] == otherPoint[1]:
                    continue
                
                if (point[0], otherPoint[1]) in pointsSet and (otherPoint[0], point[1]) in pointsSet:
                    area = abs(point[0] - otherPoint[0]) * abs(point[1] - otherPoint[1])
                    if area < minArea:
                        minArea = area

        return minArea if minArea != math.inf else 0

class LonelyPointsHelper:
    def createCoordinateIndex(self, points):
            xIndex = collections.defaultdict(set)
            yIndex = collections.defaultdict(set)

            for x,y in points:
                xIndex[x].add(y)
                yIndex[y].add(x)

            return (xIndex, yIndex)
    
    def findLonelyPoints(self, xIndex, yIndex):
            lonelyPoints = set()

            for x, yCoordinates in xIndex.items():
                if len(yCoordinates) == 1:
                    lonelyPoint = (x, next(iter(xIndex[x])))
                    lonelyPoints.add(lonelyPoint)

            for y, xCoordinates in yIndex.items():
                if len(xCoordinates) == 1:
                    lonelyPoint = (next(iter(yIndex[y])), y)
                    lonelyPoints.add(lonelyPoint)

            return lonelyPoints

    def deletePointFromCoordinateIndex(self, x, y, xIndex, yIndex):
        """
        Removes the given point from the xIndex and yIndex.
        Removing can create an extra lonely point. If that is the case, we return it
        and the caller needs to call this function again with that point. The reason is
        that deleting the new lonely point can create a chain reaction.
        """
        xIndex[x].remove(y)
        yIndex[y].remove(x)

        lonelyPoint = None

        if len(xIndex[x]) == 0:
            del xIndex[x]
        elif len(xIndex[x]) == 1:
            lonelyPoint = (x, next(iter(xIndex[x])))

        if len(yIndex[y]) == 0:
            del yIndex[y]
        elif len(yIndex[y]) == 1:
            lonelyPoint = (next(iter(yIndex[y])), y)

        return lonelyPoint
    
    def deleteLonelyPoints(self, xIndex, yIndex, lonelyPoints, pointsIndex):
        """
        If pointsIndex is passed, then we delete lonely points, otherwise we
        ignore it.
        """
        while lonelyPoints:
            x,y = lonelyPoints.pop()

            if pointsIndex:
                pointsIndex.discard((x,y))

            newLonelyPoint = self.deletePointFromCoordinateIndex(x, y, xIndex, yIndex)
            if newLonelyPoint:
                lonelyPoints.add(newLonelyPoint)

class Solution2:
    def minAreaRect(self, points: List[List[int]]) -> int:
        """
        This is an optimization where we remove lonely points.

        Index all points by x and y. Delete all the points that are alone 
        by either coordinate. This will create a chain reaction since there
        will be new points that are alone.

        I think that after this process we should only have rectangles remaining.
        """
        
        lonelyPointsHelper = LonelyPointsHelper()

        xIndex, yIndex = lonelyPointsHelper.createCoordinateIndex(points)

        lonelyPoints = lonelyPointsHelper.findLonelyPoints(xIndex, yIndex)

        lonelyPointsHelper.deleteLonelyPoints(xIndex, yIndex, lonelyPoints, None)

        pointsOfRectangles = set()
        for x, yCoordinates in xIndex.items():
            for y in yCoordinates:
                pointsOfRectangles.add((x,y))

        minArea = None
        while pointsOfRectangles:
            # We don't need to keep the point once we process it. Given that we will consider
            # all the rectables where this point will be present. But we can't delete the other
            # points of the rectangles because they can be part of other rectangles that don't
            # have the current point. This chnages the runtime a lot.
            point = pointsOfRectangles.pop()
            x,y = point
            for otherPoint in pointsOfRectangles:
                # This will cover 2 cases: the point is the same or the points have the same x or y.
                if x == otherPoint[0] or y == otherPoint[1]:
                    continue
                
                if (x, otherPoint[1]) in pointsOfRectangles and (otherPoint[0], y) in pointsOfRectangles:
                    area = abs(x - otherPoint[0]) * abs(y - otherPoint[1])
                    if minArea == None or area < minArea:
                        minArea = area
            
            # We delete the point of the indexes and trigger the chain effect to delete all the lonely points.
            # This is optional, but it improves the runtime 10-20%

            lonelyPoint = lonelyPointsHelper.deletePointFromCoordinateIndex(x, y, xIndex, yIndex)
            if lonelyPoint:
                lonelyPointsHelper.deleteLonelyPoints(xIndex, yIndex, set([lonelyPoint]), pointsOfRectangles)

        return minArea or 0

class Solution:
    def minAreaRect(self, points):
        """
        The approach of this solution comes from:
        https://leetcode.com/problems/minimum-area-rectangle/solutions/192021/python-o-n-1-5-80ms/
        
        It has the best runtime.

        Instead of analyzing from the POV of a point, it analyzes from the POV of a given coordinate
        and doing a left-right swipe if we choose the x coordinate or a bottom-up swipe if we choose the 
        y coordinate. We should choose the coordiante with more cardinality. The reason is evident when
        we explain the approach.

        Say it goes left to right, for a given value of x, we create all the pairs of values of y.
        Say we have points: (0,1),(0,3),(0,4),(0,7),(1,3),(1,7).
        We will create the following pairs:        
        For x=0: (1,3), (1,4), (1,7), (3,4), (3,7), (4,7)
        For x=1: (3,7)
        When we go from left to right, we keep track of the last value of x for a given pair. When we find that
        pair again, we know that there will be a rectangle, and we know that the minimum area will be with the
        last occurrence of that pair.
        Of course the current pair can form a rectangle with a pair on the right that we haven't seen, but when
        we go through that pair, then we will calculate the area of that rectangle.

        Interestingly, runtime is not improved noticeably by removing lonely points.
        """
        removeLonelyPoints = True
        if removeLonelyPoints:
            lonelyPointsHelper = LonelyPointsHelper()
            xIndex, yIndex = lonelyPointsHelper.createCoordinateIndex(points)
            
            lonelyPoints = lonelyPointsHelper.findLonelyPoints(xIndex, yIndex)
            lonelyPointsHelper.deleteLonelyPoints(xIndex, yIndex, lonelyPoints, None)

            coordinateIndex = xIndex if len(xIndex) > len(yIndex) else yIndex
        else:
            # If we don't want to remove lonely points, the runtime seems to improve a little bit.
            # I'm guessing that most of the test cases don't have a lot of extra points. Or, the extra points
            # don't affect the runtime on this approach compared to the approach that uses points as POV.
            # But given that I still don't get the same runtime as the solution from the link, we can use
            # the same approach the link uses to figure out which coordinate to use, which avoids creating 2 indexes 
            # of points but it will create 2 extra sets and do an extra pass.
            # Removing lonely points gives me 98.2% often. Not removing lonely points gives me
            # 98.8-99.03% now and then with either of the below 2 approaches.
            # I tried the approach from the link because the solution gets 99.15% often. But the slightly better 
            # runtime doesn't seem to be coming from this part of the code.
            # Another thing I do different is that I'm deleting coordinates when I do coordinateIndex[x].pop().
            # But the solution of the link is doing an extra sort instead so I'm surprised that that approach
            # is more efficient.
            # I tried the 2 different ways to iterate coordinateIndex in Solution4 and Solution5 and the results aren't
            # still conclusive. 
            # I don't want to spend much more time trying to figure out where that <1% improvement comes from, otherwise
            # I could copy and paste that solution and incrementally modify it to become my solution and testing it along
            # the way.
            createBothIndexes = False
            if createBothIndexes:
                lonelyPointsHelper = LonelyPointsHelper()
                xIndex, yIndex = lonelyPointsHelper.createCoordinateIndex(points)
                coordinateIndex = xIndex if len(xIndex) > len(yIndex) else yIndex
            else:
                xCardinality = len(set(x for x,y in points))
                yCardinality = len(set(y for x,y in points))
                
                coordinateIndex = collections.defaultdict(set)
                if len(xCardinality) > len(yCardinality):
                    for x,y in points:
                        coordinateIndex[x].add(y)
                else:
                    for x,y in points:
                        coordinateIndex[y].add(x)

        minArea = math.inf
        lastSeenIndex = dict()
        for x in sorted(coordinateIndex):
            while coordinateIndex[x]:
                y1 = coordinateIndex[x].pop()
                for y2 in coordinateIndex[x]:
                    yPair = (y1, y2) if y1 < y2 else (y2, y1)
                    if yPair in lastSeenIndex:
                        # Can also use yPair[1] - yPair[0] instead of abs(y2 - y1)
                        area = abs(y2 - y1) * (x - lastSeenIndex[yPair])
                        minArea = min(minArea, area)

                    lastSeenIndex[yPair] = x

        return minArea if minArea != math.inf else 0

class Solution4:
    """
    Same as Solution3 but cleaning the clutter and choosing specific strategies.
    """
    def minAreaRect(self, points):
        xCardinality = len(set(x for x,y in points))
        yCardinality = len(set(y for x,y in points))

        n = len(points)
        if xCardinality == n or yCardinality == n:
            return 0

        coordinateIndex = collections.defaultdict(list)
        if xCardinality >= yCardinality:
            for x,y in points:
                coordinateIndex[x].append(y)
        else:
            for x,y in points:
                coordinateIndex[y].append(x)

        minArea = math.inf
        lastSeenIndex = dict()
        for x in sorted(coordinateIndex):
            while coordinateIndex[x]:
                y1 = coordinateIndex[x].pop()
                for y2 in coordinateIndex[x]:
                    yPair = (y1, y2) if y1 < y2 else (y2, y1)
                    if yPair in lastSeenIndex:
                        area = abs(y2 - y1) * (x - lastSeenIndex[yPair])
                        minArea = min(minArea, area)

                    lastSeenIndex[yPair] = x

        return minArea if minArea != math.inf else 0

class Solution5:
    """
    Same as Solution3 but cleaning the clutter and choosing specific strategies.
    """
    
    def minAreaRect(self, points):
        xCardinality = len(set(x for x,y in points))
        yCardinality = len(set(y for x,y in points))

        n = len(points)
        if xCardinality == n or yCardinality == n:
            return 0

        coordinateIndex = collections.defaultdict(list)
        if xCardinality >= yCardinality:
            for x,y in points:
                coordinateIndex[x].append(y)
        else:
            for x,y in points:
                coordinateIndex[y].append(x)

        minArea = math.inf
        lastSeenIndex = dict()
        for x in sorted(coordinateIndex):
            coordinateIndex[x].sort()
            for i in range(len(coordinateIndex[x])):
                for j in range(i+1, len(coordinateIndex[x])):
                    # since we are sorting, y1 <= y2
                    y1 = coordinateIndex[x][i]
                    y2 = coordinateIndex[x][j]
                    yPair = (y1, y2)
                    if yPair in lastSeenIndex:
                        area = (y2 - y1) * (x - lastSeenIndex[yPair])
                        minArea = min(minArea, area)

                    lastSeenIndex[yPair] = x

        return minArea if minArea != math.inf else 0
17600