Leetcode 963. Minimum Area Rectangle II

Problem Explanation

Given a set of points on a 2D plane, the goal is to find and return the minimum area of any rectangle that can be formed from these points. The sides of the rectangle do not need to be parallel to the x and y axes. If there is not possible rectangle that can be formed, the function should return 0.

For example, let's say you have the following set of points: [[1,2],[2,1]]

In this example, a rectangle cannot be formed, so the function will return 0.

Solution Approach

The solution iterates through all pairs of points to form centers. It then uses a hash to group pairs of points that have the same center. Once we have the center-to-points hash, we then iterate for all pair points (AC and AD in the solution) that share the same center. If the dot product of AC and AD equals 0, it means AC is perpendicular to AD (Remembers the properties of vectors? A dot product of two vector is zero if and only if they are perpendicular). That means we can form a rectangle. So, we calculate the area of the rectangle and compare it with the smallest area we've obtained so far, and keep the smallest one. After checking all pairs, if we have no valid rectangle found, return 0. Otherwise, return the square root of the smallest area (since we are actually comparing the square of distance / area).

The data structure used is a hash table (unordered_map in C++, dictionary in Python) to map from a center to a set of points. And the algorithms involved are basic geometry and vector algebra.

Example

Let's walk through an example:

Input: [[1,2],[2,1],[1,0],[0,1]]

1. Iterate through all pairs of points and form a center. We get: (2,1) and (1,1) have the same center (1.5, 1.5).
2. Then, for the points that share center (1.5, 1.5), by checking their dot product, we can find that (2,1) and (0,1) can form a rectangle with (1,2) and (1,0).
3. Calculate areas of all valid rectangles and find the smallest one, which is 2.

Following this, we return our answer, which in this case is 2.

Python Solution

1
2python
3
4import inf
5  
6class Solution:
7    def minAreaFreeRect(self, points_list):
8        points = set(map(tuple, points_list))
9        centerX = 0
10        centerY = 0
11        min_area = inf
12        for a in range(len(points_list)):
13            p1 = points_list[a]
14            for b in range(a):
15                p2 = points_list[b]
16                for c in range(b):
17                    p3 = points_list[c]
18                    p4 = (
19                        p2[0] + p3[0] - p1[0],
20                        p2[1] + p3[1] - p1[1]
21                    )
22                    if p4 in points:
23                        vectors = (
24                            p2[0] - p1[0],
25                            p2[1] - p1[1],
26                            p3[0] - p1[0],
27                            p3[1] - p1[1]
28                        )
29                        if vectors[0] * vectors[2] + vectors[1] * vectors[3] == 0:
30                            area = ((vectors[0]**2 + vectors[1]**2) * (vectors[2]**2 + vectors[3]**2))**0.5
31                            if area < min_area:
32                                min_area = area
33                                centerX = (p1[0] + p4[0]) / 2.0
34                                centerY = (p1[1] + p4[1]) / 2.0
35        return min_area if min_area < inf else 0

C++ Solution

1
2cpp
3#include<bits/stdc++.h>
4typedef long long int64;
5const int MAX=55;
6const double EPS=1e-8;
7using namespace std;
8
9class Solution {
10public:
11    double minAreaFreeRect(vector<vector<int>>& points) {
12        int n=points.size();
13        // the key is the line passing through the centers of rectangles.
14        // the value is the set of lengths between points and the line center.
15        unordered_map<int64, unordered_map<int64, vector<int>>> center_lines;
16        for (int i=1; i<n; ++i)
17            for (int j=0; j<i; ++j) {
18                int64 x0 = points[i][0]+points[j][0];
19                int64 y0 = points[i][1]+points[j][1];
20                center_lines[((x0)<<30)|y0][(points[i][0]-points[j][0])*(points[i][0]-points[j][0])
21                                             +(points[i][1]-points[j][1])*(points[i][1]-points[j][1])].push_back(i*n+j);
22            }
23
24        double min_area = INT_MAX;
25        for (auto &p:center_lines)
26            for (auto &q:p.second)
27                if (q.second.size()>1) {
28                    int m=q.second.size();
29                    vector<double> A(m, 0);  // angles
30                    for (int i=0; i<m; ++i) {
31                        int x = q.second[i]/n;
32                        int y = q.second[i]%n;
33                        double dx = points[x][0]-points[y][0];
34                        double dy = points[x][1]-points[y][1];
35                        A[i] = atan2(dy, dx);
36                    }
37                    sort(A.begin(), A.end());
38                    for (int i=1; i<m; ++i)
39                        min_area = min(min_area, A[i]-A[i-1]);
40                    min_area = min(min_area, 2*acos(-1)+A[0]-A[m-1]);
41                }
42
43        return min_area==INT_MAX?0:sqrt(min_area);
44    }
45};

Java Solution

1
2java
3class Solution {
4    public double minAreaFreeRect(int[][] points) {
5        int len = points.length;
6        double min = Double.MAX_VALUE;
7        Map<String, List<int[]>> map = new HashMap<>();
8        for (int i = 0;i < len;i++) {
9            for (int j = i + 1;j < len;j++) {
10                long dis = distance(points[i], points[j]);
11                double centerX = (double)(points[j][0] + points[i][0]) / 2;
12                double centerY = (double)(points[j][1] + points[i][1]) / 2;
13                String key = "" + dis + "+" + centerX + "+" + centerY;
14                if (map.containsKey(key)) {
15                    List<int[]> pairs = map.get(key);
16                    for (int[] pair:pairs) {
17                        double area = Math.sqrt(distance(points[pair[0]], points[i]) *
18                                        distance(points[pair[1]], points[j]));
19                        min = Math.min(min, area);
20                    }
21                }
22                map.putIfAbsent(key, new ArrayList<>());
23                map.get(key).add(new int[] {i, j});
24            }
25        }
26        return min < Double.MAX_VALUE ? min : 0;
27    }
28
29    private long distance(int[] p1, int[] p2) {
30        long dx = p1[0] - p2[0], dy = p1[1] - p2[1];
31        return dx * dx + dy * dy;
32    }
33}

Javascript Solution

1
2javascript
3var minAreaFreeRect = function(points) {
4    let map = new Map()
5    for(let p1 of points){
6        for(let p2 of points){
7            if(p1[0] === p2[0] && p1[1] === p2[1]) continue
8            let c = [(p1[0] + p2[0])/2, (p1[1] + p2[1])/2] 
9            let d = Math.pow((p1[1] - p2[1]), 2) + Math.pow(p1[0] - p2[0], 2)
10            if(!map.has(c))map.set(c, new Map())
11            if(!map.get(c).has(d))map.get(c).set(d, [])
12            map.get(c).get(d).push([p1, p2])
13        }
14    }
15    let minArea = Infinity;
16    for(let pairs of map.values()){
17        for(let ppairs of pairs.values()){
18            if(ppairs.length < 2) continue
19            for(let k = 0; k < ppairs.length - 1; k++){
20                for(let j = k + 1; j < ppairs.length; j++){
21                    let d1 = Math.pow((ppairs[k][0][0] - ppairs[j][0][0]), 2) + Math.pow(ppairs[k][0][1] - ppairs[j][0][1], 2)
22                    let d2 = Math.pow((ppairs[k][0][0] - ppairs[j][1][0]), 2) + Math.pow(ppairs[k][0][1] - ppairs[j][1][1], 2)
23                    let area = Math.sqrt(d1) * Math.sqrt(d2)
24                    minArea = Math.min(minArea, area)
25                }
26            }
27        }
28    }
29    return minArea === Infinity ? 0 : minArea
30};

C# Solution

1
2csharp
3public class Solution {
4    public double MinAreaFreeRect(int[][] points) {
5        double min = double.MaxValue;
6        Dictionary<string, IList<(int,int)>> map = new Dictionary<string,IList<(int, int)>>();
7        int n = points.Length;
8        for(int i = 0;i < n; i++){
9            for(int j = i+1; j < n;j++){
10                int dis = Distance(points[i], points[j]);
11                double centerX = (points[i][0]+points[j][0])/2d;
12                double centerY = (points[i][1]+points[j][1])/2d;
13                string key = dis+"_"+centerX+"_"+centerY;
14                if(!map.ContainsKey(key))
15                    map[key] = new List<(int,int)>();
16                    map[key].Add((i,j));
17            }
18        }
19
20        foreach(var pair in map.Values){
21            for(int i = 0;i < pair.Count;i++){
22                for(int j = i+1;j < pair.Count;j++){
23                    var l1 = pair[i];
24                    var l2 = pair[j];
25                    int dis1 = Distance(points[l1.Item1],points[l2.Item1]);
26                    int dis2 = Distance(points[l1.Item2],points[l2.Item2]);
27                    min = Math.Min(min,Math.Sqrt(dis1)*Math.Sqrt(dis2));
28                }
29            }
30        }
31
32        return min == double.MaxValue ? 0 : min;
33    }
34
35    private int Distance(int[] p1, int[] p2){
36        return (p1[0]-p2[0])*(p1[0]-p2[0])+(p1[1]-p2[1])*(p1[1]-p2[1]);
37    }
38}

Now, you must be wondering how this solution works?

So, we're taking every pair of points and calculating the center point, distance (which represents the diagonal of the rectangle), and storing it in a HashMap.

In the hashmap (centerX, centerY) are the indexes of two points, and distance from these two points is taken as a key.

Now, we iterate over every pair in the HashMap, and for every pair, we calculate the other two sides using the Pythagorean theorem and calculate the area of the rectangle formed. We keep track of the minimum area.

At the end, we return the smallest area. If no rectangle was formed, we return 0.

Storing points in HashSet

One critical point to understand here is how the points are stored using in a HashSet. The points are being stored as strings in the format "x_y". This allows constant look-up time for any specific point while preventing duplicates from being stored in the set.

Time and Space Complexity

The time complexity for this approach is O(n^2), where n is the number of points. This complexity is due to the fact we're looping through every possible pair of points to calculate the distance and center.

The space complexity will also be O(n^2) due to the need to store each pair of points in a hash map.

Final thoughts

This problem is a classic example of making use of complete search (brute force) alongside some clever observations and basic linear algebra to come up with an efficient solution. The difficulty arises in deciding what information to store (in this case, the center point and distance) and how to effectively search that information (using two pointers to search all pairs).

As with many problems, the best way to understand the solution given here is to walk through it with a few more example sets and even consider edge cases. Understanding the processes applied will give you more insight into such problems and help you develop solutions of your own.

The javascript solution first transforms the original array of points to a hashmap, where the key is the center and the diagonal of each rectangle and the value is the list of those rectangles. Then it calculates the area of every valid rectangle and finds the smallest one. The solutions in C++ and Python follow a similar approach. The Java and C# Solutions use a hashmap along with an arraylist to store and calculate the points.

Each solution uses slightly different methods but all based on the same idea, that a rectangle can be formed using a pair of diagonals. The main takeaway from this is that regardless of your programming language, understanding the problem and knowing your available data structures and how to use them can always lead to a solution.