Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/939.html
939. Minimum Area Rectangle (Medium)
Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes.
If there isn’t any rectangle, return 0.
Example 1:
Input: [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4
Example 2:
Input: [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Output: 2
Note:
1 <= points.length <= 500
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
- All points are distinct.
Solution 1.
-
class Solution { public int minAreaRect(int[][] points) { TreeMap<Integer, List<Integer>> treeMap = new TreeMap<Integer, List<Integer>>(); for (int[] point : points) { int x = point[0], y = point[1]; List<Integer> list = treeMap.getOrDefault(x, new ArrayList<Integer>()); list.add(y); treeMap.put(x, list); } int minArea = Integer.MAX_VALUE; HashMap<String, Integer> hashMap = new HashMap<String, Integer>(); Set<Integer> xValuesSet = treeMap.keySet(); for (int x : xValuesSet) { List<Integer> list = treeMap.get(x); Collections.sort(list); int size = list.size(); for (int i = 0; i < size; i++) { int y1 = list.get(i); for (int j = i + 1; j < size; j++) { int y2 = list.get(j); String positionKey = Arrays.toString(new int[]{y1, y2}); if (hashMap.containsKey(positionKey)) minArea = Math.min(minArea, (x - hashMap.get(positionKey)) * (y2 - y1)); hashMap.put(positionKey, x); } } } return minArea == Integer.MAX_VALUE ? 0 : minArea; } } ############ 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; } }
-
// OJ: https://leetcode.com/problems/transpose-matrix/ // Time: O(N^2logN) // * each point is visited only once with another point -> O(N^2) // * ys2.find(y) -> O(logN) // Space: O(N) class Solution { public: int minAreaRect(vector<vector<int>>& points) { int ans = INT_MAX; unordered_map<int, set<int>> m; for (auto &p : points) m[p[0]].insert(p[1]); for (auto i = m.begin(); i != m.end(); ++i) { auto &ys1 = i->second; for (auto j = next(i); j != m.end(); ++j) { auto &ys2 = j->second; int xDist = abs(i->first - j->first); int prevY = INT_MIN; int minYDist = INT_MAX; for (auto &y : ys1) { if (ys2.find(y) == ys2.end()) continue; if (prevY != INT_MIN) { minYDist = min(minYDist, y - prevY); } prevY = y; } if (minYDist != INT_MAX) ans = min(ans, xDist * minYDist); } } return ans == INT_MAX ? 0 : ans; } };
-
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 ############ class Solution(object): def minAreaRect(self, points): """ :type points: List[List[int]] :rtype: int """ points = map(tuple, points) points.sort() pset = set(points) N = len(points) res = float('inf') for i in range(N - 1): p1 = points[i] for j in range(i + 1, N): p4 = points[j] if p4[0] == p1[0] or p4[1] == p1[1]: continue p2 = (p1[0], p4[1]) p3 = (p4[0], p1[1]) if p2 in pset and p3 in pset: res = min(res, abs(p3[0] - p1[0]) * abs(p2[1] - p1[1])) return res if res != float("inf") else 0
-
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 } func min(a, b int) int { if a < b { return a } return b }