LC 0939 [M] Minimum Area Rectangle - ALawliet/algorithms GitHub Wiki

T: O(n^2)
S: O(n)

we use a tuple (x,y) so we can hash the coords in a set and fast lookup to prune for valid points

a rectangle has 90 degree points: (x1, y1), (x2, y2), (x1, y2), (x2, y1)

In order to form a rectangle, you need four points all positioned at 90 degrees to each other.

In this approach, we store all given points in a set.

Then iteratively go through all the points in two loops (x1, y1) and (x2, y2) while checking if (x1, y2) and (x2, y1) are also valid points. If so, we found a rectangle.

We calculate the area of this rectangle. If this area is smaller than the minimum area seen so far, make it the minimum area.

class Solution:
    def minAreaRect(self, points: List[List[int]]) -> int:
        min_area = sys.maxsize
        points_set = set()
        
        for x, y in points:
            points_set.add( (x, y) )
            
        for x1, y1 in points: # 1st point
            for x2, y2 in points: # 2nd point
                if x2 > x1 and y2 > y1: # to skip dupes for 1st and 2nd points
                    if (x1, y2) in points_set and (x2, y1) in points_set: # alternate x,y for 3rd and 4th points are valid if in set
                        area = (x2 - x1) * (y2 - y1) # abs is not necessary
                        # if area:
                        min_area = min(area, min_area)
                            
        return 0 if min_area == sys.maxsize else min_area

'''
Sort by column
1. When we see new x point, we establish base point x as baseX.
2. For every baseX, there will be multiple y points (y_for_baseX array)
3. If y was registered in previous base(for base in y_for_baseX), we update res.
  - In other words, we update res if (y, base) seen before at another x.
4. We also update x value of seen[base][y]
5. After processing, we append y to bases array.
6. Return res
'''

class Solution:
    def minAreaRect(self, points: List[List[int]]) -> int:
        base_x_to_y = collections.defaultdict(dict)
        y_for_base_x = []
        base_x = -1
        min_area = float('inf')
        for x, y in sorted(points):
            if x != base_x: # 1
                base_x = x # 1
                y_for_base_x = [] # 2
            for prev_base_x in y_for_base_x: # 3
                if y in base_x_to_y[prev_base_x]: # 3
                    area = (x - base_x_to_y[prev_base_x][y]) * (y - prev_base_x)
                    min_area = min(min_area, area) # 3
                base_x_to_y[prev_base_x][y] = x # 4
            y_for_base_x.append(y) # 5
        return min_area if min_area < float('inf') else 0 # 6

class Solution(object):
    def minAreaRect(self, points):
        columns = collections.defaultdict(list)
        for x, y in points:
            columns[x].append(y)
        lastx = {}
        ans = float('inf')

        for x in sorted(columns):
            column = columns[x]
            column.sort()
            for j, y2 in enumerate(column):
                for i in xrange(j):
                    y1 = column[i]
                    if (y1, y2) in lastx:
                        ans = min(ans, (x - lastx[y1,y2]) * (y2 - y1))
                    lastx[y1, y2] = x
        return ans if ans < float('inf') else 0