Minimum Area Rectangle II Solution in Java

Problem Description

Ah, the classic “Minimum Area Rectangle II” problem! It’s like trying to find the smallest piece of land to build your dream house, but instead of a cozy abode, you’re just trying to find a rectangle that can be formed by a set of points on a 2D plane. Imagine you’re at a party, and you want to find the smallest dance floor that can fit four of your friends who are standing at random spots. The catch? They must form a rectangle!

In this problem, you are given a set of points, and your task is to find the minimum area of a rectangle that can be formed using these points as its corners. But wait, there’s a twist! The rectangle can be rotated, so you can’t just rely on the axis-aligned rectangles you learned about in school.

Code Solution


class Solution {
  public double minAreaFreeRect(int[][] points) {
    Long ans = Long.MAX_VALUE;
    Map> centerToPoints = new HashMap<>();

    for (int[] A : points)
      for (int[] B : points) {
        int center = hash(A, B);
        if (centerToPoints.get(center) == null)
          centerToPoints.put(center, new ArrayList<>());
        centerToPoints.get(center).add(new int[] {A[0], A[1], B[0], B[1]});
      }

    for (List pointPairs : centerToPoints.values())
      for (int[] ab : pointPairs)
        for (int[] cd : pointPairs) {
          final int ax = ab[0], ay = ab[1];
          final int cx = cd[0], cy = cd[1];
          final int dx = cd[2], dy = cd[3];
          if ((cx - ax) * (dx - ax) + (cy - ay) * (dy - ay) == 0) {
            Long squaredArea = dist(ax, ay, cx, cy) * dist(ax, ay, dx, dy);
            if (squaredArea > 0)
              ans = Math.min(ans, squaredArea);
          }
        }

    return ans == Long.MAX_VALUE ? 0 : Math.sqrt(ans);
  }

  private int hash(int[] p, int[] q) {
    return ((p[0] + q[0]) << 16) + (p[1] + q[1]);
  }

  private Long dist(long px, long py, long qx, long qy) {
    return (px - qx) * (px - qx) + (py - qy) * (py - qy);
  }
}

Approach Explanation

The code above employs a clever approach to tackle the problem. It uses a hash map to group pairs of points that share the same center. For each pair of points, it checks if there exists another pair that forms a rectangle with them. The key condition is that the diagonals of the rectangle must be perpendicular, which is checked using the dot product. If a valid rectangle is found, the area is calculated, and the minimum area is updated accordingly.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n²)
Space Complexity	O(n)

Real-World Example

Imagine you’re at a park with your friends, and you want to set up a picnic area. You have a few blankets (points) laid out randomly. You want to find the smallest rectangular area that can fit all your blankets, but you can rotate them to fit better. This problem is akin to that scenario, where you need to find the optimal arrangement of your picnic blankets!

Language Links

If you want to explore solutions in other languages, check out the links below: