-
Notifications
You must be signed in to change notification settings - Fork 383
Expand file tree
/
Copy pathMinimum Area Rectangle.java
More file actions
29 lines (29 loc) · 935 Bytes
/
Minimum Area Rectangle.java
File metadata and controls
29 lines (29 loc) · 935 Bytes
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) {
Map<Integer, List<Integer>> rows = new TreeMap();
// Map of key as x coordinate and value as list of y coordinates
for (int[] point: points) {
int x = point[0];
int y = point[1];
rows.computeIfAbsent(x, k -> new ArrayList()).add(y);
}
int ans = Integer.MAX_VALUE;
Map<String, Integer> lastX = new HashMap();
for (int x: rows.keySet()) {
List<Integer> row = rows.get(x);
Collections.sort(row);
for (int i = 0; i < row.size(); ++i) {
for (int j = i + 1; j < row.size(); ++j) {
int y1 = row.get(i);
int y2 = row.get(j);
String code = y1 + ":" + y2;
if (lastX.containsKey(code)) {
ans = Math.min(ans, (x - lastX.get(code)) * (y2 - y1));
}
lastX.put(code, x);
}
}
}
return ans < Integer.MAX_VALUE ? ans : 0;
}
}