medium Minimum Area Rectangle

Problem Statement

Given an array of points in the X-Y plane points where points[i] = [xi, yi], return the minimum area of a rectangle formed from these points. The sides of the rectangle should be parallel to the X and Y axes. If there is not any such rectangle, return 0.

Examples

1. Example 1:

   • Input:: points = [[1,2],[2,1],[1,0],[0,1]]
   • Expected Output:: 0
   • Justification:: There are no four points that can form a rectangle with sides parallel to the axes, so the minimum area is 0.

2. Example 2:

   • :Input:: points = [[0,1],[0,3],[3,1],[3,3],[4,1],[4,3]]
   • :Expected Output:: 2
   • :Justification:: These points form a rectangle with corners at [3,1], [4,1], [4,3], and [3,3]. This rectangle's area is 2, making it the smallest possible area from these points.

3. Example 3:

   • :Input:: points = [[1,1],[2,2],[3,3]]
   • :Expected Output:: 0
   • :Justification:: There are no four points that can form a rectangle with sides parallel to the axes, so the minimum area is 0.

Solution

To solve this problem, we will use a hash set to efficiently check whether a pair of points that could form the opposite corners of a rectangle exist. The core idea is to iterate through all possible pairs of points and use these as potential opposite corners of a rectangle. For each pair, we check if the other two corners (which complete the rectangle) are present in our set of points. This approach works well because checking for the existence of a point in a hash set is an O(1) operation, making the overall algorithm efficient.

The effectiveness of this approach lies in its ability to quickly determine potential rectangles by focusing on opposite corners. Since the sides of the rectangle are parallel to the axes, the X and Y coordinates of the corners provide a straightforward way to identify the missing corners if two opposite ones are known. This method is efficient for sparse point sets where not every combination of points forms a rectangle, thereby reducing unnecessary checks.

Step-by-Step Algorithm

1. Initialize a Set:

   • Create an empty set to store all the input points for quick lookup. This set will help us check the existence of points in constant time.

2. Iterate Through All Pairs of Points:

   • Use a nested loop to iterate through every pair of points from the input. These points are considered as potential opposite corners of a rectangle.

3. Check for Potential Rectangles:

   • For each pair of points (p1, p2) being considered, ensure they are not on the same horizontal or vertical line, i.e., p1.x != p2.x && p1.y != p2.y.This check is crucial because, for a rectangle formed with sides parallel to the axes, opposite corners must have different x and y coordinates.

4. Calculate the Other Two Corners:

   • For a pair of points (p1, p2) that passes the previous check, calculate the coordinates of the other two corners of the potential rectangle. These coordinates are (p1.x, p2.y) and (p2.x, p1.y).

5. Check for the Existence of the Other Two Corners:

   • Use the set created in step 1 to check if both of these calculated points exist. If both points are present in the set, it confirms the presence of a rectangle.

6. Calculate the Rectangle's Area:

   • If a rectangle is confirmed, calculate its area by multiplying the absolute difference in x-coordinates by the absolute difference in y-coordinates of any two adjacent corners.

7. Track the Minimum Area:

   • Maintain a variable to keep track of the minimum area of all rectangles found. Update this variable whenever a smaller area is calculated.

8. Return the Result:

   • After iterating through all pairs of points, return the minimum area found. If no rectangle was formed (the minimum area was not updated), return 0.

Algorithm Walkthrough

Let's consider the Input: nums = [[0,1],[0,3],[3,1],[3,3],[4,1],[4,3]].

1. Convert Points to a Set: First, all points are added to a set for efficient lookup. This step is essential for quickly determining if the complementary points (other two corners) of a rectangle exist.

2. Iterate Over All Pairs of Points: We compare each pair of points to see if they can potentially form opposite corners of a rectangle.

• Process [0, 1]:
  • Pair [[0,1],[0,3]]: Not valid because they share the same x-coordinate. Opposite corners of a rectangle must have different x and y coordinates.
  • Pair [[0,1],[3,1]]: Not valid because they share the same y-coordinate. Opposite corners of a rectangle must have different x and y coordinates.
  • Pair [[0,1],[3,3]]: This is a potential pair of opposite corners. We look for points [0,3] and [3,1], which exist. Area = (3-0) * (3-1) = 6.
  • Pair [[0,1],[4,1]]: Not valid because they share the same y-coordinate.
  • Pair [[0,1],[4,3]]: This is a potential pair, but it essentially outlines the same rectangle as [[0,1],[3,3]] and [[4,1],[3,3]], only larger, if considering [0,3] and [4,1] as the other two points. Area = (4-0) * (3-1) = 8.
• Process [0, 3]:
  • Pair [[0,3],[3,1]]: This is a potential pair of opposite corners. We look for points [0,1] and [3,3], which exist. Area = (3-0) * (3-1) = 6.
  • Pair [[0,3],[3,3]]: Not valid because they share the same y-coordinate.
  • Pair [[0,3],[4,1]]: This is a potential pair of opposite corners. We look for points [0,1] and [4,3], which exist. Area = (4-0) * (3-1) = 8.
  • Pair [[0,3],[4,3]]: Not valid because they share the same y-coordinate.
• Process [3, 1]:
  • Pair [[3,1],[3,3]]: Not valid because they share the same x-coordinate.
  • Pair [[3,1],[4,1]]: Not valid because they share the same y-coordinate.
  • Pair [[3,1],[4,3]]: This is a potential pair of opposite corners. We look for points [3,3] and [4,1], which exist. Area = (4-3) * (3-1) = 2.
• Process [3, 1]:
  • Pair [[3,3],[4,1]]: This is a potential pair of opposite corners. We look for points [3,1] and [4,3], which exist. Area = (4-3) * (3-1) = 2.
  • Pair [[3,3],[4,3]]: Not valid because they share the same y-coordinate.
• Process [4, 1]:
  • Pair [[4,1],[4,3]]: Not valid because they share the same x-coordinate.

1. Determine the Smallest Area: From the valid rectangles identified, the one formed by the points [3,1], [4,3], [3,3], and [4,1] has the smallest area of 2. This is the minimum area rectangle that can be formed with the given points.

Code

import java.util.HashSet;
import java.util.Set;

public class Solution {

  public int minAreaRect(int[][] points) {
    Set<String> pointSet = new HashSet<>();
    for (int[] point : points) {
      // Convert each point to a string and add it to the set for quick lookup
      String pointStr = point[0] + "," + point[1];
      pointSet.add(pointStr);
    }

    int minArea = Integer.MAX_VALUE;
    for (int i = 0; i < points.length; i++) {
      for (int j = 0; j < points.length; j++) {
        if (i != j) {
          // Check if the current pair of points can form diagonal corners of a rectangle
          int[] p1 = points[i];
          int[] p2 = points[j];
          if (p1[0] != p2[0] && p1[1] != p2[1]) {
            // Check if the other two corners of the rectangle exist
            String corner1 = p1[0] + "," + p2[1];
            String corner2 = p2[0] + "," + p1[1];
            if (pointSet.contains(corner1) && pointSet.contains(corner2)) {
              // Calculate area of the rectangle
              int area = Math.abs(p1[0] - p2[0]) * Math.abs(p1[1] - p2[1]);
              minArea = Math.min(minArea, area);
            }
          }
        }
      }
    }
    // Return the smallest area found, or 0 if no rectangle can be formed
    return minArea == Integer.MAX_VALUE ? 0 : minArea;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Example 1
    System.out.println(
      solution.minAreaRect(
        new int[][] { { 1, 2 }, { 2, 1 }, { 1, 0 }, { 0, 1 } }
      )
    ); // 0
    // Example 2
    System.out.println(
      solution.minAreaRect(
        new int[][] {
          { 0, 1 },
          { 0, 3 },
          { 3, 1 },
          { 3, 3 },
          { 4, 1 },
          { 4, 3 },
        }
      )
    ); // 2
    // Example 3
    System.out.println(
      solution.minAreaRect(new int[][] { { 1, 1 }, { 2, 2 }, { 3, 3 } })
    ); // 0
  }
}

Complexity Analysis

Time Complexity

The time complexity of the algorithm is primarily determined by the double loop used to iterate through all pairs of points, which gives us , where n is the number of points. For each pair, we perform a constant time operation to check if the complementary points forming the rectangle exist in the set. Thus, the overall time complexity remains .

Space Complexity

The space complexity is , where n is the number of points. This is due to the storage of all points in a hash set (or an equivalent data structure) to allow for constant time lookups. The space used by the set is directly proportional to the number of points, thus making the space complexity linear.