939 Minimum Area Rectangle

link: Minimum Area Rectangle

Thought

I plan to use sweep line to solve. Firstly I put a dictionary with x-val as key, all y-val with coordinate x-val as value. Then, once I check x1, x2, if they has intersection, means there could be a rectangle. So I could enumerate all possible rectangles and record the smallest one. 

Code

class Solution:
    def minAreaRect(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        if not points or len(points) < 4:
            return 0
        res = 0
        lookup = collections.defaultdict(set)
        minimum = 2**32
        for node in points:
            lookup[node[0]].add(node[1])
        keys = list(lookup.keys())
        keys.sort()
        for j in range(len(keys)):
            for i in range(j):
                cross = list(lookup[keys[i]].intersection(lookup[keys[j]]))
                if len(cross) >= 2:
                    cross.sort()
                    for k in range(len(cross) - 1):
                        if (cross[k + 1] - cross[k]) * (keys[j] - keys[i]) < minimum:
                            minimum = (cross[k + 1] - cross[k]) * (keys[j] - keys[i])
                            res = minimum
        return res

Runtime

Time: O(n^3)
Space: O(n)