963. Minimum Area Rectangle II LeetCode Solution

In this guide, you will get 963. Minimum Area Rectangle II LeetCode Solution with the best time and space complexity. The solution to Minimum Area Rectangle II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Minimum Area Rectangle II solution in C++
4. Minimum Area Rectangle II solution in Java
5. Minimum Area Rectangle II solution in Python
6. Additional Resources

Problem Statement of Minimum Area Rectangle II

You are given an array of points in the X-Y plane points where points[i] = [xi, yi].
Return the minimum area of any rectangle formed from these points, with sides not necessarily parallel to the X and Y axes. If there is not any such rectangle, return 0.
Answers within 10-5 of the actual answer will be accepted.

Example 1:

Input: points = [[1,2],[2,1],[1,0],[0,1]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [1,2],[2,1],[1,0],[0,1], with an area of 2.

Example 2:

Input: points = [[0,1],[2,1],[1,1],[1,0],[2,0]]
Output: 1.00000
Explanation: The minimum area rectangle occurs at [1,0],[1,1],[2,1],[2,0], with an area of 1.

Example 3:

Input: points = [[0,3],[1,2],[3,1],[1,3],[2,1]]
Output: 0
Explanation: There is no possible rectangle to form from these points.

Constraints:

1 <= points.length <= 50
points[i].length == 2
0 <= xi, yi <= 4 * 104
All the given points are unique.

Complexity Analysis

• Time Complexity: O(n^6)
• Space Complexity: O(n^2)

963. Minimum Area Rectangle II LeetCode Solution in C++

class Solution {
 public:
  double minAreaFreeRect(vector<vector<int>>& points) {
    long ans = LONG_MAX;
    // For each A, B pair points, {hash(A, B): (ax, ay, bx, by)}.
    unordered_map<int, vector<tuple<int, int, int, int>>> centerToPoints;

    for (const vector<int>& A : points)
      for (const vector<int>& B : points) {
        const int center = hash(A, B);
        centerToPoints[center].emplace_back(A[0], A[1], B[0], B[1]);
      }

    // For all pair points "that share the same center".
    for (const auto& [_, points] : centerToPoints)
      for (const auto& [ax, ay, bx, by] : points)
        for (const auto& [cx, cy, dx, dy] : points)
          // AC is perpendicular to AD.
          // AC dot AD = (cx - ax, cy - ay) dot (dx - ax, dy - ay) == 0.
          if ((cx - ax) * (dx - ax) + (cy - ay) * (dy - ay) == 0) {
            const long squaredArea =
                dist(ax, ay, cx, cy) * dist(ax, ay, dx, dy);
            if (squaredArea > 0)
              ans = min(ans, squaredArea);
          }

    return ans == LONG_MAX ? 0 : sqrt(ans);
  }

 private:
  int hash(const vector<int>& p, const vector<int>& q) {
    return ((long)(p[0] + q[0]) << 16) + (p[1] + q[1]);
  }

  long dist(int px, int py, int qx, int qy) {
    return (px - qx) * (px - qx) + (py - qy) * (py - qy);
  }
};
/* code provided by PROGIEZ */

963. Minimum Area Rectangle II LeetCode Solution in Java

class Solution {
  public double minAreaFreeRect(int[][] points) {
    long ans = Long.MAX_VALUE;
    // For each A, B pair points, {hash(A, B): (ax, ay, bx, by)}.
    Map<Integer, List<int[]>> 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 all pair points "that share the same center".
    for (List<int[]> 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];
          // AC is perpendicular to AD.
          // AC dot AD = (cx - ax, cy - ay) dot (dx - ax, dy - ay) == 0.
          if ((cx - ax) * (dx - ax) + (cy - ay) * (dy - ay) == 0) {
            final 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);
  }
}
// code provided by PROGIEZ

963. Minimum Area Rectangle II LeetCode Solution in Python

class Solution:
  def minAreaFreeRect(self, points: list[list[int]]) -> float:
    ans = math.inf
    # For each A, B pair points, {hash(A, B): (ax, ay, bx, by)}.
    centerToPoints = collections.defaultdict(list)

    for ax, ay in points:
      for bx, by in points:
        center = ((ax + bx) / 2, (ay + by) / 2)
        centerToPoints[center].append((ax, ay, bx, by))

    def dist(px: int, py: int, qx: int, qy: int) -> float:
      return (px - qx)**2 + (py - qy)**2

    # For all pair points "that share the same center".
    for points in centerToPoints.values():
      for ax, ay, _, _ in points:
        for cx, cy, dx, dy in points:
          # AC is perpendicular to AD.
          # AC dot AD = (cx - ax, cy - ay) dot (dx - ax, dy - ay) == 0.
          if (cx - ax) * (dx - ax) + (cy - ay) * (dy - ay) == 0:
            squaredArea = dist(ax, ay, cx, cy) * dist(ax, ay, dx, dy)
            if squaredArea > 0:
              ans = min(ans, squaredArea)

    return 0 if ans == math.inf else math.sqrt(ans)
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.