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. 1 <= points.length <= 500
  2. 0 <= points[i][0] <= 40000
  3. 0 <= points[i][1] <= 40000
  4. 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
    }
    

All Problems

All Solutions