Minimum Area Rectangle

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

We need to count each rectangle by right-most edge. 

  1. Group the y points by x coordinates, so that we have columns of points. <X,[List of Y]>
  2. Then, for every pair of points in a column (with coordinates (x,y1) and (x,y2)), check for the smallest rectangle with this pair of points as the rightmost edge. We can do this by keeping the memory of what pairs of points we’ve seen before.
Minimum Area Rectangle
class Solution {
    public int minAreaRect(int[][] points) {
        
        if(points.length == 0 || points[0].length == 0){
            return 0;
        }
        Map<Integer, List<Integer>> map = new TreeMap<>();
        for(int[] point : points){
            int x = point[0];
            int y = point[1];
            List<Integer> yList = map.get(x);
            if(yList == null){
                yList = new ArrayList<>();
                map.put(x, yList);
            }
            yList.add(y);
        }
        int minArea = Integer.MAX_VALUE;
        Map<String, Integer> seenX = new HashMap<>();
        for(int x : map.keySet()){
            List<Integer> yList = map.get(x);
            Collections.sort(yList);
            int size = yList.size();
            for(int i = 0 ; i < size ; i++){
                int y1 = yList.get(i);
                for(int j = i+1 ; j < size ; j++){
                    int y2 = yList.get(j);
                    String key = y1 +"_" + y2;
                    if(seenX.containsKey(key)){
                        int prev_x = seenX.get(key);
                        minArea = Math.min(minArea, (x-prev_x) * (y2-y1));
                    }
                    seenX.put(key, x);
                }
            }
        }
        return minArea == Integer.MAX_VALUE ? 0 : minArea;
    }
}

Complexity Analysis

  • Time Complexity: O(N3), where N is the length of points.
  • Space Complexity: O(N).

‘ ​

Categories: Map

Tagged as: , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s