Massive Algorithms: LeetCode 939 - Minimum Area Rectangle

LeetCode 939 - 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

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.

X. O(N^3)
http://www.noteanddata.com/leetcode-939-Minimum-Area-Rectangle-java-solution-note.html

有三层循环，最差情况下可能会到O(N^3), 但是实际可能并不会那么差，因为每层循环不可能同时很大

public int minAreaRect(int[][] points) {
    Map<Integer, List<int[]>> xmap = new HashMap<>();
    Map<Integer, List<int[]>> ymap = new HashMap<>();
    Map<Integer, Map<Integer, int[]>> xymap = new HashMap<>();
    for(int[] point: points) {
        int x= point[0], y = point[1];
        List<int[]> list1 = xmap.get(x);
        if(list1 == null) {
            list1 = new ArrayList<>();
            xmap.put(x, list1);
        }
        
        list1.add(point);
        
        List<int[]> list2 = ymap.get(y);            
        if(null == list2) {
            list2 = new ArrayList<>();
            ymap.put(y, list2);
        }
        list2.add(point);
        
        Map<Integer, int[]> map = xymap.get(x);
        if(null == map) {
            map = new HashMap<>();
            xymap.put(x, map);
        }
        map.put(y, point);
    }
    
    int minArea = Integer.MAX_VALUE;
    for(int x1: xmap.keySet()) {
        List<int[]> list1 = xmap.get(x1);
        
        for(int i = 0; i < list1.size(); ++i) {
            for(int j = i+1; j < list1.size(); ++j) {
                int[] pi = list1.get(i);
                int[] pj = list1.get(j);
                List<int[]> pplist = ymap.get(pi[1]);
                if(null == pplist) continue;
                for(int[] pp: pplist) {
                    int x = pp[0];
                    Map<Integer, int[]> map = xymap.get(x);
                    if(null == map) continue;

                    int y = pj[1];
                    
                    int[] pq = map.get(y);
                    if(null == pq) continue;

                    int diffx = pp[0] - pi[0];
                    int diffy = pj[1] - pi[1];

                    int area = Math.abs(diffx * diffy);
                    if(area == 0) continue;
                    minArea = Math.min(area, minArea);
                }                                        
            }
        }
    }
    
    if(minArea == Integer.MAX_VALUE) {
        return 0;
    }
    return minArea;
}

https://buptwc.com/2018/11/11/Leetcode-939-Minimum-Area-Rectangle/

在所有点中找出四个点，使其能够构成一个平行于坐标轴的矩形，求可能构成的矩形的最小面积。

我们先用两个字典将所有的点按照横坐标和纵坐标记录下来
我们用dx[i]表示在x= i这条线上的所有点的纵坐标，用dy[i]表示在y=i这条线上所有点的纵坐标，那么对于示例1:，有：
dx = {1: [1,3], 2:[2], 3:[1,3]}
dy = {1: [1,3], 2:[2], 3:[1,3]}

我们如何去寻找矩形的四个点呢？

在dx中选定一个x
在dx[x]中选定两个不同的y，分别为y1,y2
在dy[y1]中找到一个x1，且 x1 != x
最后判断 x1,y2 是否存在于points当中。
若存在，计算面积
若不存在，go to step 1

def minAreaRect(points):
    s = set(map(tuple, points))
    dx = collections.defaultdict(list)
    dy = collections.defaultdict(list)
    for x,y in points:
        dx[x].append(y)
        dy[y].append(x)

    res = float('inf')
    # 1. 确定x
    for x in sorted(dx.keys()):
        # 2.确定y1
        for i in range(len(dx[x])):
            y1 = dx[x][i]
            # 确定y2
            for j in range(i+1, len(dx[x])):
                y2 = dx[x][j]
                # 3. 寻找x1
                for x1 in dy[y2]:
                    if x1 == x: continue
                    # 4. 判断(x1,y1)是否在points当中
                    if (x1, y1) in s:
                        res = min(res, abs(x-x1) * abs(y1-y2))

    return res if res != float('inf') else 0

你可能会有疑问，怎么耗时这么长，那是因为会有重复计算，就比如上图中，选择x的时候作为第一步的基准的时候将这个矩形考虑了一次，选择x1作为第一步的时候又将这个矩形计算了一次，这样就会存在大量重复计算，那怎么修改呢？

关键在于我们始终选择第一步中的x作为矩形左边这条边，之后寻找的x1必须要比x大才行。
只要将if x1 == x 改为 if x1 <= x即可。

# 1300ms
import collections
def minAreaRect(points):
    s = set(map(tuple, points))
    dx = collections.defaultdict(list)
    dy = collections.defaultdict(list)
    for x,y in points:
        dx[x].append(y)
        dy[y].append(x)

    res = float('inf')
    for x in sorted(dx.keys()):
        for i in range(len(dx[x])):
            y1 = dx[x][i]
            for j in range(i+1, len(dx[x])):
                y2 = dx[x][j]
                for x1 in dy[y2]:
                    if x1 <= x: continue
                    if (x1, y1) in s:
                        res = min(res, abs(x-x1) * abs(y1-y2))

    return res if res != float('inf') else 0

X. Approach 2: Count by Diagonal

https://yeqiuquan.blogspot.com/2018/11/939-minimum-area-rectangle.html

The brute-force way is to use four for loops to iterate all four points. For each four points, we can determine whether they can form a rectangular and maintain a minimum size.

If 4 points can form a rectangular, they have to be (x₁, y₁), (x₁, y₂), (x₂, y₁), and (x₂, y₂). We can see x₁ exists twice, x₂ exists twice, y₁ exists twice and y₂ exists twice. We can implement an isValid function with this logic.

The bruce-force approach takes O(n⁴) time, which is not good.

A better solution is we can go through all points in O(n) and maintain a HashMap. For each x, we maintain a Set in the map that contains all existing y corresponding to this x.

After building up the map, we can use two for loops to choose any two points in the input. For each two points (A and B), we first determine if they are diagonal. If they are diagonal, we know these two points have different x and different y.

Then we can use the map to check:
1. there exists a point which has A's x and B's y
2. there exists a point which has B's x and A's y
3. check size

This takes O(1) time.

In this way, we can solve the problem in O(n²) time with an additional space for the map.

    public int minAreaRect(int[][] points) {
        int res = Integer.MAX_VALUE;
        HashMap<Integer, HashSet<Integer>> map = new HashMap<>();
        for (int[] point : points) {
            if (!map.containsKey(point[0])) {
                map.put(point[0], new HashSet<>());
            }
            map.get(point[0]).add(point[1]);
        }
        for (int[] pointA : points) {
            for (int[] pointB : points) {
                if (pointA[0] == pointB[0] || pointA[1] == pointB[1]) {
                    continue;
                }
                if (!map.get(pointA[0]).contains(pointB[1]) 
                    || !map.get(pointB[0]).contains(pointA[1])) {
                    continue;
                }
                res = Math.min(res, 
                               Math.abs((pointB[0] - pointA[0]) 
                                        * (pointB[1] - pointA[1])
                                        )
                              );
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }

For each pair of points in the array, consider them to be the long diagonal of a potential rectangle. We can check if all 4 points are there using a Set.

For example, if the points are (1, 1) and (5, 5), we check if we also have (1, 5) and (5, 1). If we do, we have a candidate rectangle.

Algorithm

Put all the points in a set. For each pair of points, if the associated rectangle are 4 distinct points all in the set, then take the area of this rectangle as a candidate answer.

Time Complexity: $O(N^2)$ , where $N$ is the length of points.

public int minAreaRect(int[][] points) {

Set<Integer> pointSet = new HashSet();

for (int[] point : points)

pointSet.add(40001 * point[0] + point[1]);

int ans = Integer.MAX_VALUE;

for (int i = 0; i < points.length; ++i)

for (int j = i + 1; j < points.length; ++j) {

if (points[i][0] != points[j][0] && points[i][1] != points[j][1]) {

if (pointSet.contains(40001 * points[i][0] + points[j][1])

&& pointSet.contains(40001 * points[j][0] + points[i][1])) {

ans = Math.min(ans, Math.abs(points[j][0] - points[i][0]) * Math.abs(points[j][1] - points[i][1]));

}

return ans < Integer.MAX_VALUE ? ans : 0;

}

https://zxi.mytechroad.com/blog/geometry/leetcode-939-minimum-area-rectangle/

Try all pairs of points to form a diagonal and see whether pointers of another diagonal exist or not.

Assume two points are (x0, y0), (x1, y1) x0 != x1 and y0 != y1. The other two points will be (x0, y1), (x1, y0)

Time complexity: O(n^2)

  int minAreaRect(vector<vector<int>>& points) {    

    unordered_map<int, unordered_set<int>> s;

    for (const auto& point : points)

      s[point[0]].insert(point[1]);

    const int n = points.size();

    int min_area = INT_MAX;

    for (int i = 0; i < n; ++i)

      for (int j = i + 1; j < n; ++j) {

        int x0 = points[i][0];

        int y0 = points[i][1];

        int x1 = points[j][0];

        int y1 = points[j][1];

        if (x0 == x1 || y0 == y1) continue;

        int area = abs(x0 - x1) * abs(y0 - y1);

        if (area > min_area) continue;

        if (!s[x1].count(y0) || !s[x0].count(y1)) continue;

        min_area = area;

}

    return min_area == INT_MAX ? 0 : min_area;

}

https://blog.csdn.net/fuxuemingzhu/article/details/83961509
确定对角线，找另外两点（4sum）
周赛的第三题，超时了很多次，确实需要优秀的解法才能通过。

最原始的想法就是，我们找出和坐标轴平行的三个点，来确定第四个点。这么做的话，时间复杂度是O(N^3)，果然超时了。这说明我对4sum理解还不够深刻啊！两天前刚做过的454. 4Sum II，做法就是确定两个数字的和，然后看剩余的两个数字的和是否存在即可。也就是说4sum的时间复杂度只有O(N^2)。

这个题正确的做法是先确定对角线两个点！题目要求所有的边必须平行坐标轴，就是告诉我们只用确定对角线两个元素，剩余的两个点可以直接求出来即可！因此不需要确定3个点的O(N^3)的遍历。

所以啊，还是需要活学活用才行啊！

题目应该说清楚：面积为0的不算长方形。这样我们才能做两个对角线点不重合的判断。

时间复杂度是O(N^2)，空间复杂度是O(N)。

http://www.noteanddata.com/leetcode-939-Minimum-Area-Rectangle-java-solution-2.html

原来暴力的做法显然不好，我们是在相同x的点里面任意取两个点，然后根据固定的y，最后在剩下的点里面看是否存在两个点符合需求。
这里主要的问题是前面两个点不能完全确定所有4个点，需要对第三个点试错以后才可以决定第4个点。
如果我们更换思路，如果取对角线的两个点，那么其实这两个点已经可以决定长方形了，
所以这里只要能够有一个map可以判断是否存在<x,y>的点，就可以判断剩下两个点是否存在。
当然，每次取对角的两个点的时候，需要跳过x或者y相同的点，因为这样没有办法组成长方形。
这里思路的核心是，如何更好的确定4个点？原来的暴力朴素的想法是，先找x坐标一样的两个点，然后在找第3个点，最后可以固定到第4个.
但是如果我们切换到通过对角的两个点，就可以直接固定这4个点，也方便很多。

xymap is too complex

public int minAreaRect(int[][] points) {
    Map<Integer, Map<Integer, int[]>> xymap = new HashMap<>();
    for(int[] point: points) {            
        Map<Integer, int[]> map = xymap.get(point[0]);
        if(null == map) {
            map = new HashMap<>();
            xymap.put(point[0], map);
        }
        map.put(point[1], point);
    }
    
    int minArea = Integer.MAX_VALUE;
    for(int i = 0;i < points.length; ++i) {
        for(int j = i+1; j < points.length; ++j) {
            if(points[i][0] == points[j][0] || points[i][1] == points[j][1])  { // same x or  same y, not Diagonal points
                continue;
            }
            // exist other two points if diagonal exist
            if(xymap.get(points[i][0]).containsKey(points[j][1]) && xymap.get(points[j][0]).containsKey(points[i][1])) {
                int area = (points[i][0] - points[j][0]) * (points[i][1] - points[j][1]);
                minArea = Math.min(minArea, Math.abs(area));                    
            }                
        }
    }        
    
    if(minArea == Integer.MAX_VALUE) {
        return 0;
    }
    return minArea;
}

Approach 1: Sort by Column

Count each rectangle by right-most edge.

Algorithm

Group the points by x coordinates, so that we have columns of points. 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 memory of what pairs of points we've seen before.

Time Complexity: $O(N^2)$ , where $N$ is the length of points.

public int minAreaRect(int[][] points) {

Map<Integer, List<Integer>> rows = new TreeMap();

for (int[] point : points) {

int x = point[0], y = point[1];

rows.computeIfAbsent(x, z -> new ArrayList()).add(y);

}

int ans = Integer.MAX_VALUE;

Map<Integer, 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), y2 = row.get(j);

int code = 40001 * 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;

}

X. Brute Force

https://leetcode.com/problems/minimum-area-rectangle/discuss/192025/Java-N2-Hashmap

Nice idea to figure out the diagonal points! That is what is all needed to compute the area. Also when you look at that line if (map.get(p1[0]).contains(p2[1]) && map.get(p2[0]).contains(p1[1])) its amazing how the symmetry plays itself in the expression p1[0]-p2[1] and p2[0]-p1[1].

    public int minAreaRect(int[][] points) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] p : points) {
            if (!map.containsKey(p[0])) {
                map.put(p[0], new HashSet<>());
            }
            map.get(p[0]).add(p[1]);
        }
        int min = Integer.MAX_VALUE;
        for (int[] p1 : points) {
            for (int[] p2 : points) {
                if (p1[0] == p2[0] || p1[1] == p2[1]) { // if have the same x or y
                    continue;
                }
                if (map.get(p1[0]).contains(p2[1]) && map.get(p2[0]).contains(p1[1])) { // find other two points
                    min = Math.min(min, Math.abs(p1[0] - p2[0]) * Math.abs(p1[1] - p2[1]));
                }
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }

https://blog.csdn.net/bob__yuan/article/details/83989719

https://leetcode.com/problems/minimum-area-rectangle/discuss/192021/Python-O(N1.5)-80ms

N = 500 is really loose.
Brute force, check all pairs of points.
O(N^2) , 1000ms ~ 1200ms

    def minAreaRect(self, points):
        seen = set()
        res = float('inf')
        for x1, y1 in points:
            for x2, y2 in seen:
                if (x1, y2) in seen and (x2, y1) in seen:
                    area = abs(x1 - x2) * abs(y1 - y2)
                    if area and area < res:
                        res = area
            seen.add((x1, y1))
        return res if res < float('inf') else 0

Another idea is that,
For each x value in sorted order, check all y pairs.

In most cases, all points randomly distribute.
Only 500 points in 40001 * 40001 possible coordinates.
No two points will have the same x value or y value.
There will be no rectangle and the result is 0.
This will be O(N) solution.

However, it seems that, in the test cases, it has a really big amount of rectangles.
In these worst cases, the time complexity is O(nx * nx * ny) < O(N ^ 1.5).

In the extreme worst cases, like all points have x = 0 or y = 0
Time complexity will be O(N^2)

O(N^1.5), 80ms

    def minAreaRect(self, points):
        n = len(points)
        nx = len(set(x for x, y in points))
        ny = len(set(y for x, y in points))
        if nx == n or ny == n:
            return 0

        p = collections.defaultdict(list)
        if nx > ny:
            for x, y in points:
                p[x].append(y)
        else:
            for x, y in points:
                p[y].append(x)

        lastx = {}
        res = float('inf')
        for x in sorted(p):
            p[x].sort()
            for i in range(len(p[x])):
                for j in range(i):
                    y1, y2 = p[x][j], p[x][i]
                    if (y1, y2) in lastx:
                        res = min(res, (x - lastx[y1, y2]) * (y2 - y1))
                    lastx[y1, y2] = x
        return res if res < float('inf') else 0

LeetCode 939 - Minimum Area Rectangle

Labels

Popular Posts