Problem Description

You are given a set of points in the 2D plane, represented as a list of points where each point is a pair [x, y] of integers. Your task is to find the minimum area of a rectangle formed by any four of these points, where the sides of the rectangle are parallel to the x and y axes. Each rectangle must have its four corners among the given points. If no such rectangle can be formed, return 0.

• You cannot reuse points; each corner must be a distinct point from the input.
• The rectangle's sides must be parallel to the axes (not slanted).
• Return 0 if there are no valid rectangles.

Thought Process

The brute-force way would be to check every quadruple of points to see if they form a rectangle, but this is highly inefficient as the number of quadruples grows rapidly with the number of points. Instead, we can look for patterns: for rectangles aligned with the axes, their sides are parallel to the axes, which means the rectangle is defined by two distinct x-values and two distinct y-values. If we can find two pairs of points that share the same x or y coordinates, we can check whether the other two corners exist.

The key insight is: for any pair of points that are diagonally opposite corners of a rectangle, if the other two required corners exist in the set, then a rectangle is formed. To make lookups fast, we can use a set to store all points for constant-time existence checks.

Instead of checking all quadruples, we can iterate over all pairs of points and, for each diagonal pair, check whether the other two corners exist. This brings the complexity down significantly, especially with the help of a set for quick lookups.

Solution Approach

• Store all input points in a set (or hash map) for O(1) lookups.
• Iterate over all pairs of points. For each pair (x1, y1) and (x2, y2):
  • Only consider pairs where x1 != x2 and y1 != y2, ensuring they are diagonally opposite corners.
  • Check if the other two corners (x1, y2) and (x2, y1) exist in the set.
  • If they do, compute the area as abs(x1 - x2) * abs(y1 - y2).
  • Keep track of the minimum area found.
• After checking all pairs, return the minimum area (or 0 if none found).
• This approach avoids redundant checks (e.g., by only considering pairs where x1 < x2 and y1 < y2).

Using a set for point existence checks is crucial for efficiency, reducing the time to check the presence of a point from O(n) to O(1).

Example Walkthrough

Sample Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]

1. Store all points in a set for quick lookup.
2. Pick the first pair: (1,1) and (3,3) (diagonal corners).
   • Check if (1,3) and (3,1) exist in the set. They do.
   • Compute area: abs(1-3) * abs(1-3) = 2 * 2 = 4.
   • Update minimum area to 4.
3. Try other pairs like (1,1) and (2,2), but the other required corners do not exist.
4. Continue for all pairs. No rectangle with smaller area is found.
5. Return the minimum area found, which is 4.

Time and Space Complexity

• Brute-force approach: O(n⁴) time, since it checks every quadruple of points.
• Optimized approach: O(n²) time, since it checks every pair of points (O(n²)), and for each pair, checks the existence of two points in O(1) time.
• Space complexity: O(n) for storing all points in a set.

The optimized solution is much faster and feasible for the typical input constraints of this problem.

Summary

The key to solving the Minimum Area Rectangle problem efficiently is recognizing that rectangles aligned with the axes can be detected by checking pairs of diagonal corners and confirming the presence of the other two corners. By leveraging a set for constant-time lookups and iterating over all pairs, we reduce the complexity from O(n⁴) to O(n²). This approach is both elegant and practical, making it suitable for real-world inputs.

Code Implementation

class Solution:
    def minAreaRect(self, points):
        point_set = set((x, y) for x, y in points)
        min_area = float('inf')
        n = len(points)
        for i in range(n):
            x1, y1 = points[i]
            for j in range(i+1, n):
                x2, y2 = points[j]
                # Check for diagonal (not on same row or column)
                if x1 != x2 and y1 != y2:
                    if (x1, y2) in point_set and (x2, y1) in point_set:
                        area = abs(x1 - x2) * abs(y1 - y2)
                        if area < min_area:
                            min_area = area
        return 0 if min_area == float('inf') else min_area
      

class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        set<pair<int, int>> pointSet;
        for (auto& p : points) {
            pointSet.insert({p[0], p[1]});
        }
        int minArea = INT_MAX;
        int n = points.size();
        for (int i = 0; i < n; ++i) {
            int x1 = points[i][0], y1 = points[i][1];
            for (int j = i + 1; j < n; ++j) {
                int x2 = points[j][0], y2 = points[j][1];
                if (x1 != x2 && y1 != y2) {
                    if (pointSet.count({x1, y2}) && pointSet.count({x2, y1})) {
                        int area = abs(x1 - x2) * abs(y1 - y2);
                        if (area < minArea) minArea = area;
                    }
                }
            }
        }
        return minArea == INT_MAX ? 0 : minArea;
    }
};
      

import java.util.*;
class Solution {
    public int minAreaRect(int[][] points) {
        Set<String> pointSet = new HashSet<>();
        for (int[] p : points) {
            pointSet.add(p[0] + "," + p[1]);
        }
        int minArea = Integer.MAX_VALUE;
        int n = points.length;
        for (int i = 0; i < n; ++i) {
            int x1 = points[i][0], y1 = points[i][1];
            for (int j = i + 1; j < n; ++j) {
                int x2 = points[j][0], y2 = points[j][1];
                if (x1 != x2 && y1 != y2) {
                    if (pointSet.contains(x1 + "," + y2) && pointSet.contains(x2 + "," + y1)) {
                        int area = Math.abs(x1 - x2) * Math.abs(y1 - y2);
                        if (area < minArea) minArea = area;
                    }
                }
            }
        }
        return minArea == Integer.MAX_VALUE ? 0 : minArea;
    }
}
      

var minAreaRect = function(points) {
    const pointSet = new Set(points.map(p => p[0] + ',' + p[1]));
    let minArea = Infinity;
    const n = points.length;
    for (let i = 0; i < n; ++i) {
        let [x1, y1] = points[i];
        for (let j = i + 1; j < n; ++j) {
            let [x2, y2] = points[j];
            if (x1 !== x2 && y1 !== y2) {
                if (pointSet.has(x1 + ',' + y2) && pointSet.has(x2 + ',' + y1)) {
                    let area = Math.abs(x1 - x2) * Math.abs(y1 - y2);
                    if (area < minArea) minArea = area;
                }
            }
        }
    }
    return minArea === Infinity ? 0 : minArea;
};