Geometry
Array
Hash Table
Math
Sorting
Description
You are given an array of points in the X-Y plane points
where points[i] = [xi , yi ]
.
Return the minimum area of a rectangle formed from these points, with sides parallel to the X and Y axes . If there is not any such rectangle, return 0
.
Example 1:
Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4
Example 2:
Input: points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Output: 2
Constraints:
1 <= points.length <= 500
points[i].length == 2
0 <= xi , yi <= 4 * 104
All the given points are unique .
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution :
def minAreaRect ( self , points : List [ List [ int ]]) -> int :
d = defaultdict ( list )
for x , y in points :
d [ x ] . append ( y )
pos = {}
ans = inf
for x in sorted ( d ):
ys = d [ x ]
ys . sort ()
n = len ( ys )
for i , y1 in enumerate ( ys ):
for y2 in ys [ i + 1 :]:
if ( y1 , y2 ) in pos :
ans = min ( ans , ( x - pos [( y1 , y2 )]) * ( y2 - y1 ))
pos [( y1 , y2 )] = x
return 0 if ans == inf else ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 class Solution {
public int minAreaRect ( int [][] points ) {
TreeMap < Integer , List < Integer >> d = new TreeMap <> ();
for ( var p : points ) {
int x = p [ 0 ] , y = p [ 1 ] ;
d . computeIfAbsent ( x , k -> new ArrayList <> ()). add ( y );
}
Map < Integer , Integer > pos = new HashMap <> ();
int ans = 1 << 30 ;
for ( var e : d . entrySet ()) {
int x = e . getKey ();
var ys = e . getValue ();
Collections . sort ( ys );
int n = ys . size ();
for ( int i = 0 ; i < n ; ++ i ) {
int y1 = ys . get ( i );
for ( int j = i + 1 ; j < n ; ++ j ) {
int y2 = ys . get ( j );
int p = y1 * 40001 + y2 ;
if ( pos . containsKey ( p )) {
ans = Math . min ( ans , ( x - pos . get ( p )) * ( y2 - y1 ));
}
pos . put ( p , x );
}
}
}
return ans == 1 << 30 ? 0 : ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 class Solution {
public :
int minAreaRect ( vector < vector < int >>& points ) {
map < int , vector < int >> d ;
for ( auto & p : points ) {
int x = p [ 0 ], y = p [ 1 ];
d [ x ]. emplace_back ( y );
}
unordered_map < int , int > pos ;
int ans = 1 << 30 ;
for ( auto & [ x , ys ] : d ) {
sort ( ys . begin (), ys . end ());
int n = ys . size ();
for ( int i = 0 ; i < n ; ++ i ) {
int y1 = ys [ i ];
for ( int j = i + 1 ; j < n ; ++ j ) {
int y2 = ys [ j ];
int p = y1 * 40001 + y2 ;
if ( pos . count ( p )) {
ans = min ( ans , ( x - pos [ p ]) * ( y2 - y1 ));
}
pos [ p ] = x ;
}
}
}
return ans == 1 << 30 ? 0 : ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 func minAreaRect ( points [][] int ) int {
d := map [ int ][] int {}
xs := [] int {}
for _ , p := range points {
x , y := p [ 0 ], p [ 1 ]
d [ x ] = append ( d [ x ], y )
}
for x := range d {
xs = append ( xs , x )
}
sort . Ints ( xs )
type pair struct { x , y int }
pos := map [ pair ] int {}
ans := 1 << 30
for _ , x := range xs {
ys := d [ x ]
sort . Ints ( ys )
for i , y1 := range ys {
for _ , y2 := range ys [ i + 1 :] {
p := pair { y1 , y2 }
if x1 , ok := pos [ p ]; ok {
ans = min ( ans , ( x - x1 ) * ( y2 - y1 ))
}
pos [ p ] = x
}
}
}
if ans == 1 << 30 {
return 0
}
return ans
}
GitHub