Minimum Area Rectangle

medium hash set geometry points

Problem

You are given an array of points in the X-Y plane. Return the minimum area of any axis-aligned rectangle whose four corners are all in the given points, or 0 if no such rectangle exists.

Inputpoints = [[1,1],[1,3],[3,1],[3,3],[2,2]]

Output4

The corners (1,1), (1,3), (3,1), (3,3) form a 2 × 2 square with area 4. The point (2,2) is not a corner of any rectangle.

points (e.g. [[1,1],[1,3],[3,1],[3,3]])

def min_area_rect(points):
    seen = set(map(tuple, points))
    best = float("inf")
    for i in range(len(points)):
        x1, y1 = points[i]
        for j in range(i):
            x2, y2 = points[j]
            if x1 != x2 and y1 != y2:
                if (x1, y2) in seen and (x2, y1) in seen:
                    area = abs(x1 - x2) * abs(y1 - y2)
                    best = min(best, area)
    return best if best != float("inf") else 0

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

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

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

Explanation

An axis-aligned rectangle is fully determined by just two opposite corners on a diagonal. If we pick points (x1,y1) and (x2,y2) as a diagonal, the other two corners must be (x1,y2) and (x2,y1). So we just check whether those two also exist.

We hash every point into a set for instant lookups. Then we try every pair of points as a diagonal. A valid diagonal needs different x's and different y's (x1 != x2 and y1 != y2); otherwise the points share a row or column and can't be opposite corners.

When both partner corners are present in the set, we have a real rectangle. Its area is |x1 - x2| * |y1 - y2|, and we keep the smallest area seen.

Example: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]. The diagonal (1,1)–(3,3) needs corners (1,3) and (3,1), both present, giving area 2 * 2 = 4. The stray point (2,2) never completes a rectangle. Answer: 4.

If no pair ever completes a rectangle, we return 0. Checking all pairs makes this O(n²), with set lookups keeping each check constant.

Time: O(n²) Space: O(n)