# Minimum Area Rectangle
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-area-rectangle)
Canonical: https://scaleengineer.com/dsa/problems/minimum-area-rectangle
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance), [Flipkart](https://scaleengineer.com/companies/flipkart), [Snap](https://scaleengineer.com/companies/snap), [Verily](https://scaleengineer.com/companies/verily)
---
## Problem
You are 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, with sides parallel to the X and Y axes_. If there is not any such rectangle, return `0`.

**Example 1:**

![](https://assets.glich.co/dsa/minimum-area-rectangle/image0.JPG) 

**Input:** points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
**Output:** 4

**Example 2:**

![](https://assets.glich.co/dsa/minimum-area-rectangle/image1.JPG) 

**Input:** points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
**Output:** 2

**Constraints:**

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

# Approaches
## Brute-force with Three Points
This approach iterates through all possible combinations of three points from the input array. For each triplet, it checks if they can form three corners of a rectangle with sides parallel to the X and Y axes. If they do, it calculates the coordinates of the required fourth point and checks for its existence.
**Time:** `O(N^3)`. Three nested loops run through the points, and the operations inside are constant time on average (due to `HashSet`). · **Space:** `O(N)` to store the points in a `HashSet`.
**Pros:** More efficient than a naive `O(N^4)` approach.; Conceptually simple to understand as a brute-force improvement.
**Cons:** `O(N^3)` is too slow for the given constraints (`N <= 500`), likely resulting in a 'Time Limit Exceeded' error.; The implementation logic can be complex with many cases to check for each triplet.
### Explanation
First, to allow for quick lookups, all the given points are stored in a `HashSet`. A point `(x, y)` can be stored as a string `"x,y"` or by encoding it into a single integer `x * 40001 + y` since coordinates are non-negative and `y <= 40000`.
The algorithm then uses three nested loops to pick three distinct points, `p1(x1, y1)`, `p2(x2, y2)`, and `p3(x3, y3)`. For each triplet, we check if they form a right-angled corner. For example, if `p1` and `p2` are aligned vertically (`x1 == x2`) and `p1` and `p3` are aligned horizontally (`y1 == y3`), then they form a right angle at `p1`. The fourth point required to complete the rectangle would be `p4(x3, y2)`. We then check if `p4` exists in our `HashSet`. If it does, we have found a valid rectangle. We calculate its area as `|x1 - x3| * |y1 - y2|` and update our minimum area found so far. This process is repeated for all possible triplets and all possible corner configurations within the triplet.

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

class Solution {
    public int minAreaRect(int[][] points) {
        Set<Integer> pointSet = new HashSet<>();
        for (int[] point : points) {
            pointSet.add(point[0] * 40001 + point[1]);
        }

        int minArea = Integer.MAX_VALUE;
        int n = points.length;

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

                    // Check all 3 possibilities for the corner point
                    minArea = Math.min(minArea, check(p1, p2, p3, pointSet));
                    minArea = Math.min(minArea, check(p2, p1, p3, pointSet));
                    minArea = Math.min(minArea, check(p3, p1, p2, pointSet));
                }
            }
        }

        return minArea == Integer.MAX_VALUE ? 0 : minArea;
    }

    private int check(int[] p1, int[] p2, int[] p3, Set<Integer> pointSet) {
        int x1 = p1[0], y1 = p1[1];
        int x2 = p2[0], y2 = p2[1];
        int x3 = p3[0], y3 = p3[1];

        // Check if p2 and p3 form a right angle at p1
        if (x1 == x2 && y1 == y3) {
            // Fourth point is (x3, y2)
            if (pointSet.contains(x3 * 40001 + y2)) {
                return Math.abs(x1 - x3) * Math.abs(y1 - y2);
            }
        }
        return Integer.MAX_VALUE;
    }
}
```
### Algorithm
*   Store all points in a `HashSet` for efficient `O(1)` average time lookups.
*   Initialize `minArea` to `Integer.MAX_VALUE`.
*   Use three nested loops to iterate through all unique triplets of points `(p1, p2, p3)`.
*   For each triplet, check if they can form a right-angled corner. For example, if `p1` and `p2` are aligned vertically (`p1.x == p2.x`) and `p1` and `p3` are aligned horizontally (`p1.y == p3.y`), they form a right angle at `p1`.
*   If they do, the fourth point `p4` would have coordinates `(p3.x, p2.y)`.
*   Check if `p4` exists in the `HashSet`.
*   If `p4` exists, calculate the area `abs((p1.x - p3.x) * (p1.y - p2.y))` and update `minArea`.
*   This check must be performed for all three points in the triplet acting as the corner.
*   After checking all triplets, if `minArea` is still `Integer.MAX_VALUE`, return 0. Otherwise, return `minArea`.

## Group by Columns and Match Vertical Edges
This approach improves upon brute-force by organizing the points. It groups points by their x-coordinate into columns. Then, it iterates through each column, finds all possible vertical edges (pairs of points), and looks for matching vertical edges in other columns to form rectangles.
**Time:** `O(N^2)`. Let `C` be the number of columns. Pre-processing takes at most `O(N log N)`. The main loop iterates through all pairs of points that share an x-coordinate. The total number of such pairs is `sum(k_i^2)`, where `k_i` is the number of points in column `i`. This sum can be up to `O(N^2)` in the worst case. · **Space:** `O(N^2)`. The `columns` map takes `O(N)` space. However, the `lastX` map can store up to `O(N^2)` pairs of y-coordinates in the worst case, making the space complexity quadratic.
**Pros:** More structured than brute-force.; Can be faster than `O(N^2)` on certain data distributions (e.g., sparse points).
**Cons:** The worst-case space complexity of `O(N^2)` is significant and worse than other `O(N^2)` time solutions.
### Explanation
First, we process the input points and group them by their x-coordinate. A `HashMap<Integer, List<Integer>>` is a suitable data structure, mapping an x-coordinate to a list of y-coordinates present at that `x`. For each list of y-coordinates in the map, we sort it. This makes it easier to find pairs and compare them later. We then iterate through the unique x-coordinates in sorted order. For each `x`, we iterate through all pairs of y-coordinates `(y1, y2)` in its sorted list. This pair of points `(x, y1)` and `(x, y2)` forms a vertical line segment. To find a rectangle, we need to find another x-coordinate, `x_prev`, that also has points at `y1` and `y2`. To do this efficiently, we use another `HashMap<String, Integer>`, let's call it `lastX`. This map will store the most recently seen x-coordinate for a given vertical edge defined by a pair `(y1, y2)`. If we find a match in `lastX`, we've found a rectangle. By iterating `x` in sorted order, we ensure that `(x - x_prev)` is the smallest possible width for any rectangle ending at `x` with that specific vertical edge, which is key to finding the minimum area.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int minAreaRect(int[][] points) {
        Map<Integer, List<Integer>> columns = new HashMap<>();
        for (int[] p : points) {
            columns.computeIfAbsent(p[0], k -> new ArrayList<>()).add(p[1]);
        }

        List<Integer> xCoords = new ArrayList<>(columns.keySet());
        Collections.sort(xCoords);

        int minArea = Integer.MAX_VALUE;
        Map<String, Integer> lastX = new HashMap<>();

        for (int x : xCoords) {
            List<Integer> yList = columns.get(x);
            Collections.sort(yList);
            for (int i = 0; i < yList.size(); i++) {
                for (int j = i + 1; j < yList.size(); j++) {
                    int y1 = yList.get(i);
                    int y2 = yList.get(j);
                    String key = y1 + "," + y2;
                    if (lastX.containsKey(key)) {
                        int prevX = lastX.get(key);
                        int area = (x - prevX) * (y2 - y1);
                        minArea = Math.min(minArea, area);
                    }
                    lastX.put(key, x);
                }
            }
        }

        return minArea == Integer.MAX_VALUE ? 0 : minArea;
    }
}
```
### Algorithm
*   Create a `Map<Integer, List<Integer>>` called `columns` to group points by x-coordinate.
*   Iterate through the input `points` and populate `columns`.
*   Get the unique x-coordinates from `columns.keySet()` and sort them.
*   Initialize `minArea` to `Integer.MAX_VALUE` and a `Map<String, Integer>` called `lastX`.
*   Iterate through the sorted x-coordinates (`x`).
*   For each `x`, get the list of y-coordinates `yList` and sort it.
*   Use two nested loops to iterate through all pairs `(y1, y2)` in `yList` where `y1 < y2`.
*   Create a key for the pair, e.g., `String key = y1 + "," + y2;`.
*   If `lastX` contains `key`, retrieve the previous x-coordinate `x_prev = lastX.get(key)`.
*   Calculate the area `(x - x_prev) * (y2 - y1)` and update `minArea`.
*   Update `lastX` with the current `x`: `lastX.put(key, x)`.
*   After the loops, if `minArea` is `Integer.MAX_VALUE`, return 0, else return `minArea`.

## Iterate Over Diagonals
This is a highly efficient and elegant approach. It iterates through all pairs of points and considers them as potential diagonals of a rectangle. For any two points `p1(x1, y1)` and `p2(x2, y2)` to be a diagonal, the other two corners of the rectangle must be `p3(x1, y2)` and `p4(x2, y1)`. The algorithm simply checks if these two required points exist.
**Time:** `O(N^2)`. We have two nested loops to iterate through all pairs of points, which is `O(N^2)`. The operations inside the loop (set lookups, arithmetic) are constant time on average. · **Space:** `O(N)`. We use a `HashSet` to store all `N` points.
**Pros:** Optimal time complexity for this problem.; Simple and clean implementation.; Efficient `O(N)` space complexity.
**Cons:** This is the standard and best solution for the given constraints, so there are no significant cons.
### Explanation
The core idea is that any two diagonally opposite points `(x1, y1)` and `(x2, y2)` in a rectangle (with sides parallel to axes) uniquely define the other two points: `(x1, y2)` and `(x2, y1)`. To implement this, we first need a way to quickly check for the existence of a point. A `HashSet` is perfect for this, providing average `O(1)` time complexity for lookups. We pre-populate the `HashSet` with all the points from the input array. To store a 2D point in a 1D set, we can encode it into a single integer (e.g., `x * 40001 + y`, since `y <= 40000`). The algorithm then uses two nested loops to iterate through every unique pair of points, `p1` and `p2`. For each pair `p1(x1, y1)` and `p2(x2, y2)`, we check if they can form a diagonal. This is true if they are not aligned horizontally or vertically, i.e., `x1 != x2` and `y1 != y2`. If they form a potential diagonal, we construct the coordinates of the other two required points: `p3(x1, y2)` and `p4(x2, y1)`. We then query our `HashSet` to see if both `p3` and `p4` exist. If both points are found, we have identified a rectangle and calculate its area, updating the minimum area found so far.

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

class Solution {
    public int minAreaRect(int[][] points) {
        Set<Integer> pointSet = new HashSet<>();
        for (int[] point : points) {
            // Encode point (x, y) into a single integer.
            // Since y <= 40000, we can use a multiplier of 40001.
            pointSet.add(point[0] * 40001 + point[1]);
        }

        int minArea = Integer.MAX_VALUE;
        int n = points.length;

        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];

                // Check if they can form a diagonal (not aligned)
                if (x1 == x2 || y1 == y2) {
                    continue;
                }

                // Check if the other two corners exist
                // p3 is (x1, y2) and p4 is (x2, y1)
                if (pointSet.contains(x1 * 40001 + y2) && pointSet.contains(x2 * 40001 + y1)) {
                    int area = Math.abs(x1 - x2) * Math.abs(y1 - y2);
                    minArea = Math.min(minArea, area);
                }
            }
        }

        return minArea == Integer.MAX_VALUE ? 0 : minArea;
    }
}
```
### Algorithm
*   Create a `HashSet` to store all points for fast lookups. A point `(x, y)` can be encoded as a single integer or string.
*   Populate the `HashSet` with all points from the input array.
*   Initialize `minArea` to `Integer.MAX_VALUE`.
*   Use a nested loop to iterate through all pairs of points `p1(x1, y1)` and `p2(x2, y2)`.
*   Inside the loop, if `p1` and `p2` are aligned (`x1 == x2` or `y1 == y2`), skip to the next pair as they cannot form a diagonal.
*   Check if the other two corners, `(x1, y2)` and `(x2, y1)`, exist in the `HashSet`.
*   If both points exist, calculate the area: `area = Math.abs(x1 - x2) * Math.abs(y1 - y2)`.
*   Update `minArea = Math.min(minArea, area)`.
*   After the loops complete, if `minArea` is still `Integer.MAX_VALUE`, return 0. Otherwise, return `minArea`.

# Solutions
### Java

```java
class Solution {
public
  int minAreaRect(int[][] points) {
    TreeMap<Integer, List<Integer>> d = new TreeMap<>();
    for (var p : points) {
      int x = p[0], y = p[1];
      d.computeIfAbsent(x, k->new ArrayList<>()).add(y);
    }
    Map<Integer, Integer> pos = new HashMap<>();
    int ans = 1 << 30;
    for (var e : d.entrySet()) {
      int x = e.getKey();
      var ys = e.getValue();
      Collections.sort(ys);
      int n = ys.size();
      for (int i = 0; i < n; ++i) {
        int y1 = ys.get(i);
        for (int j = i + 1; j < n; ++j) {
          int y2 = ys.get(j);
          int p = y1 * 40001 + y2;
          if (pos.containsKey(p)) {
            ans = Math.min(ans, (x - pos.get(p)) * (y2 - y1));
          }
          pos.put(p, x);
        }
      }
    }
    return ans == 1 << 30 ? 0 : ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minAreaRect(vector<vector<int>> &points) {
    map<int, vector<int>> d;
    for (auto &p : points) {
      int x = p[0], y = p[1];
      d[x].emplace_back(y);
    }
    unordered_map<int, int> pos;
    int ans = 1 << 30;
    for (auto &[x, ys] : d) {
      sort(ys.begin(), ys.end());
      int n = ys.size();
      for (int i = 0; i < n; ++i) {
        int y1 = ys[i];
        for (int j = i + 1; j < n; ++j) {
          int y2 = ys[j];
          int p = y1 * 40001 + y2;
          if (pos.count(p)) {
            ans = min(ans, (x - pos[p]) * (y2 - y1));
          }
          pos[p] = x;
        }
      }
    }
    return ans == 1 << 30 ? 0 : ans;
  }
};

```

### Python

```python
class Solution:
    def minAreaRect(self, points: List[List[int]]) -> int: d = defaultdict(list) for x, y in points: d[x]. append(y) pos = {} ans = inf for x in sorted(d): ys = d[x] ys . sort() n = len(ys) for i, y1 in enumerate(ys): for y2 in ys[i + 1:]: if (y1, y2) in pos: ans = min(ans, (x - pos[(y1, y2)]) * (y2 - y1)) pos[(y1, y2)] = x return 0 if ans == inf else ans

```