> ## Content Index
> Fetch the complete content index at: https://andybase.com/llms.txt
> Use this file to discover other available public pages before exploring further.

# 939 Minimum Area Rectangle
- URL: https://andybase.com/939-minimum-area-rectangle/
- Published: 2018-11-12T18:15:28.000Z
- Updated: 2018-11-12T18:15:28.000Z
- Author: andy
- Tags: leetcode, contest, #Migrated-1784083136856, #wp, #wp-post, #Import 2026-07-15 02:38

link: [Minimum Area Rectangle](https://leetcode.com/problems/minimum-area-rectangle/?ref=andybase.com)

## 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)