# Maximum Area Rectangle With Point Constraints I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-area-rectangle-with-point-constraints-i)
Canonical: https://scaleengineer.com/dsa/problems/maximum-area-rectangle-with-point-constraints-i
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Binary Indexed Tree, Segment Tree
**Companies:** [UKG](https://scaleengineer.com/companies/ukg)
---
## Problem
You are given an array `points` where `points[i] = [xi, yi]` represents the coordinates of a point on an infinite plane.

Your task is to find the **maximum** area of a rectangle that:

* Can be formed using **four** of these points as its corners.
* Does **not** contain any other point inside or on its border.
* Has its edges **parallel** to the axes.

Return the **maximum area** that you can obtain or -1 if no such rectangle is possible.

**Example 1:**

**Input:** points = \[\[1,1\],\[1,3\],\[3,1\],\[3,3\]\]

**Output:** 4

**Explanation:**

**![Example 1 diagram](https://assets.glich.co/dsa/maximum-area-rectangle-with-point-constraints-i/image0.png)**

We can make a rectangle with these 4 points as corners and there is no other point that lies inside or on the border. Hence, the maximum possible area would be 4.

**Example 2:**

**Input:** points = \[\[1,1\],\[1,3\],\[3,1\],\[3,3\],\[2,2\]\]

**Output:**\-1

**Explanation:**

**![Example 2 diagram](https://assets.glich.co/dsa/maximum-area-rectangle-with-point-constraints-i/image1.png)**

There is only one rectangle possible is with points `[1,1], [1,3], [3,1]` and `[3,3]` but `[2,2]` will always lie inside it. Hence, returning -1.

**Example 3:**

**Input:** points = \[\[1,1\],\[1,3\],\[3,1\],\[3,3\],\[1,2\],\[3,2\]\]

**Output:** 2

**Explanation:**

**![Example 3 diagram](https://assets.glich.co/dsa/maximum-area-rectangle-with-point-constraints-i/image2.png)**

The maximum area rectangle is formed by the points `[1,3], [1,2], [3,2], [3,3]`, which has an area of 2\. Additionally, the points `[1,1], [1,2], [3,1], [3,2]` also form a valid rectangle with the same area.

**Constraints:**

* `1 <= points.length <= 10`
* `points[i].length == 2`
* `0 <= xi, yi <= 100`
* All the given points are **unique**.

# Approaches
## Brute-Force with Four-Point Combinations
This approach exhaustively checks every possible combination of four points from the input array to see if they can form a valid, empty, axis-aligned rectangle. Given the small constraint on the number of points (N <= 10), this method is feasible despite its high time complexity.
**Time:** O(N^5), where N is the number of points. There are O(N^4) combinations of four points. For each combination, we check the emptiness condition by iterating through the other O(N) points. · **Space:** O(1), as we only use a few variables to store coordinates and the max area, not dependent on the input size.
**Pros:** Simple to understand and implement.; Requires no extra space.
**Cons:** The time complexity is very high, making it impractical for larger datasets.
### Explanation
The core idea is to use brute force. Since a rectangle requires four corners, we can generate all possible sets of four points from the input list. The number of combinations is given by `N C 4`, where `N` is the total number of points. For each combination, we perform two checks:

1.  **Rectangle Formation Check:** We verify if the four points can form an axis-aligned rectangle. This is done by checking their coordinates. If there are exactly two distinct x-values and two distinct y-values among the four points, they form a rectangle.

2.  **Emptiness Check:** If the points form a rectangle, we then check if it's 'empty'. An empty rectangle is one that does not contain any *other* input points on its boundary or in its interior. We iterate through all the points in the input array that are not part of the current quartet. If any of these points fall within the rectangle's bounding box, the rectangle is invalid.

If a rectangle passes both checks, we calculate its area and update our maximum area found so far. If no such rectangle is found after checking all combinations, the initial value of -1 is returned.

```java
class Solution {
    public int maxAreaRectangle(int[][] points) {
        int n = points.length;
        if (n < 4) {
            return -1;
        }
        long maxArea = -1;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    for (int l = k + 1; l < n; l++) {
                        int[] p1 = points[i];
                        int[] p2 = points[j];
                        int[] p3 = points[k];
                        int[] p4 = points[l];

                        java.util.Set<Integer> xCoords = new java.util.HashSet<>();
                        java.util.Set<Integer> yCoords = new java.util.HashSet<>();
                        xCoords.add(p1[0]); xCoords.add(p2[0]); xCoords.add(p3[0]); xCoords.add(p4[0]);
                        yCoords.add(p1[1]); yCoords.add(p2[1]); yCoords.add(p3[1]); yCoords.add(p4[1]);

                        if (xCoords.size() == 2 && yCoords.size() == 2) {
                            int x_min = java.util.Collections.min(xCoords);
                            int x_max = java.util.Collections.max(xCoords);
                            int y_min = java.util.Collections.min(yCoords);
                            int y_max = java.util.Collections.max(yCoords);

                            boolean isEmpty = true;
                            for (int m = 0; m < n; m++) {
                                if (m == i || m == j || m == k || m == l) {
                                    continue;
                                }
                                int[] otherPoint = points[m];
                                if (otherPoint[0] >= x_min && otherPoint[0] <= x_max &&
                                    otherPoint[1] >= y_min && otherPoint[1] <= y_max) {
                                    isEmpty = false;
                                    break;
                                }
                            }

                            if (isEmpty) {
                                long area = (long)(x_max - x_min) * (y_max - y_min);
                                maxArea = Math.max(maxArea, area);
                            }
                        }
                    } 
                }
            }
        }
        return (int)maxArea;
    }
}
```
### Algorithm
*   Initialize a variable `maxArea` to -1 to store the maximum valid area found.
*   Use four nested loops to iterate through all unique combinations of four points from the input array `points`. Let the chosen points be `p1`, `p2`, `p3`, and `p4`.
*   For each quartet of points, verify if they can form an axis-aligned rectangle. This is true if the set of their x-coordinates and the set of their y-coordinates each contain exactly two unique values.
*   If they form a rectangle, determine its boundaries by finding the minimum and maximum x and y coordinates (`x_min`, `x_max`, `y_min`, `y_max`).
*   Check the emptiness condition: Iterate through all points in the original `points` array. If any point that is not one of the four corners lies within or on the boundary of the rectangle (i.e., its coordinates `(px, py)` satisfy `x_min <= px <= x_max` and `y_min <= py <= y_max`), the rectangle is considered not empty and is invalid.
*   If the rectangle is confirmed to be empty, calculate its area as `(x_max - x_min) * (y_max - y_min)`.
*   Update `maxArea` by taking the maximum of the current `maxArea` and the newly calculated area.
*   After checking all possible combinations, return the final `maxArea`.

## Optimized Approach by Checking Diagonal Pairs
A more efficient method involves iterating through all pairs of points and treating them as potential diagonal corners of a rectangle. By using a hash set for quick lookups of the other two corners, we can find candidate rectangles much faster than the four-point combination approach.
**Time:** O(N^3), where N is the number of points. We iterate through O(N^2) pairs of points. For each pair, we perform an O(1) lookup for the other corners and then an O(N) scan for the emptiness check. · **Space:** O(N) to store the N points in a `HashSet` for efficient lookups.
**Pros:** Significantly faster than the brute-force approach.; Still conceptually straightforward.
**Cons:** Requires extra space to store the points in a hash set.
### Explanation
This optimized approach reduces the complexity of finding rectangles. Instead of picking four points, we pick two points, `p1(x1, y1)` and `p2(x2, y2)`, and assume they are diagonally opposite corners. For this to be possible, their x and y coordinates must be different.

The other two corners required to complete the rectangle would be at `(x1, y2)` and `(x2, y1)`. We can check for the existence of these two points very quickly if we pre-process all input points into a `HashSet`.

Once a four-corner rectangle is identified, we perform the same emptiness check as in the brute-force approach: we iterate through all input points to ensure no other point lies within the rectangle's boundaries. If the rectangle is empty, we calculate its area and update the maximum area found.

This method reduces the complexity of finding candidate rectangles from `O(N^4)` to `O(N^2)`, leading to a significant overall performance improvement.

```java
class Solution {
    public int maxAreaRectangle(int[][] points) {
        int n = points.length;
        if (n < 4) {
            return -1;
        }

        java.util.Set<String> pointSet = new java.util.HashSet<>();
        for (int[] p : points) {
            pointSet.add(p[0] + "," + p[1]);
        }

        long maxArea = -1;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int[] p1 = points[i];
                int[] p2 = points[j];
                int x1 = p1[0], y1 = p1[1];
                int x2 = p2[0], y2 = p2[1];

                if (x1 == x2 || y1 == y2) {
                    continue;
                }

                // Check if the other two corners exist
                if (pointSet.contains(x1 + "," + y2) && pointSet.contains(x2 + "," + y1)) {
                    int x_min = Math.min(x1, x2);
                    int x_max = Math.max(x1, x2);
                    int y_min = Math.min(y1, y2);
                    int y_max = Math.max(y1, y2);

                    boolean isEmpty = true;
                    for (int[] p_check : points) {
                        boolean isCorner = (p_check[0] == x1 && p_check[1] == y1) ||
                                           (p_check[0] == x2 && p_check[1] == y2) ||
                                           (p_check[0] == x1 && p_check[1] == y2) ||
                                           (p_check[0] == x2 && p_check[1] == y1);
                        if (isCorner) {
                            continue;
                        }

                        if (p_check[0] >= x_min && p_check[0] <= x_max &&
                            p_check[1] >= y_min && p_check[1] <= y_max) {
                            isEmpty = false;
                            break;
                        }
                    }

                    if (isEmpty) {
                        long area = (long)(x_max - x_min) * (y_max - y_min);
                        maxArea = Math.max(maxArea, area);
                    }
                }
            }
        }
        return (int)maxArea;
    }
}
```
### Algorithm
*   First, store all input points in a `HashSet` to allow for constant-time average lookups. A common way to do this is to convert each point `[x, y]` into a string like `"x,y"` to use as the key.
*   Initialize a variable `maxArea` to -1.
*   Iterate through all unique pairs of points from the input array, let's say `p1 = (x1, y1)` and `p2 = (x2, y2)`.
*   For each pair, check if they can form a diagonal of an axis-aligned rectangle. This is possible only if `x1 != x2` and `y1 != y2`.
*   If they can form a diagonal, the other two corners of the rectangle would be `p3 = (x1, y2)` and `p4 = (x2, y1)`. Check if both `p3` and `p4` exist in the `HashSet`.
*   If all four corners exist, we have found a candidate rectangle. Now, check if it's empty.
*   To check for emptiness, iterate through all `N` input points. If any point (that is not one of the four corners) lies inside or on the boundary of the rectangle, the rectangle is invalid.
*   If the rectangle is empty, calculate its area: `abs(x1 - x2) * abs(y1 - y2)`.
*   Update `maxArea` with the current area if it's larger.
*   After checking all pairs, return the final `maxArea`.

# Solutions
### Java

```java
class Solution {
public
  int maxRectangleArea(int[][] points) {
    int ans = -1;
    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];
        int x3 = Math.min(x1, x2), y3 = Math.min(y1, y2);
        int x4 = Math.max(x1, x2), y4 = Math.max(y1, y2);
        if (check(points, x3, y3, x4, y4)) {
          ans = Math.max(ans, (x4 - x3) * (y4 - y3));
        }
      }
    }
    return ans;
  }
private
  boolean check(int[][] points, int x1, int y1, int x2, int y2) {
    int cnt = 0;
    for (var p : points) {
      int x = p[0];
      int y = p[1];
      if (x < x1 || x > x2 || y < y1 || y > y2) {
        continue;
      }
      if ((x == x1 || x == x2) && (y == y1 || y == y2)) {
        cnt++;
        continue;
      }
      return false;
    }
    return cnt == 4;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxRectangleArea(vector<vector<int>> &points) {
    auto check = [&](int x1, int y1, int x2, int y2) -> bool {
      int cnt = 0;
      for (const auto &point : points) {
        int x = point[0];
        int y = point[1];
        if (x < x1 || x > x2 || y < y1 || y > y2) {
          continue;
        }
        if ((x == x1 || x == x2) && (y == y1 || y == y2)) {
          cnt++;
          continue;
        }
        return false;
      }
      return cnt == 4;
    };
    int ans = -1;
    for (int i = 0; i < 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];
        int x3 = min(x1, x2), y3 = min(y1, y2);
        int x4 = max(x1, x2), y4 = max(y1, y2);
        if (check(x3, y3, x4, y4)) {
          ans = max(ans, (x4 - x3) * (y4 - y3));
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxRectangleArea(self, points: List[List[int]]) -> int: def check(x1: int, y1: int, x2: int, y2: int) -> bool: cnt = 0 for x, y in points: if x < x1 or x > x2 or y < y1 or y > y2: continue if (x == x1 or x == x2) and (y == y1 or y == y2): cnt += 1 continue return False return cnt == 4 ans = - 1 for i, (x1, y1) in enumerate(points): for x2, y2 in points[: i]: x3, y3 = min(x1, x2), min(y1, y2) x4, y4 = max(x1, x2), max(y1, y2) if check(x3, y3, x4, y4): ans = max(ans, (x4 - x3) * (y4 - y3)) return ans

```