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.

Examples

Example 1

1
2
3
4
5


![](https://assets.leetcode.com/uploads/2021/08/03/rec1.JPG)

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

Example 2

1
2
3
4
5


![](https://assets.leetcode.com/uploads/2021/08/03/rec2.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 * 10^4
  • All the given points are unique.

Solution

Method 1 – Hash Set + Pair Enumeration

Intuition

To find the minimum area rectangle, we need to find two pairs of points that share the same x or y coordinates and form the opposite corners of a rectangle. By storing all points in a set, we can efficiently check if the other two corners exist for each pair of points.

Approach

  1. Store all points in a set for O(1) lookup.
  2. For each pair of points, if they are not on the same line (x1 ≠ x2 and y1 ≠ y2), check if the other two corners (x1, y2) and (x2, y1) exist in the set.
  3. If so, compute the area and update the minimum area found.
  4. Return the minimum area, or 0 if no rectangle is found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        set<pair<int,int>> st;
        for (auto& p : points) st.insert({p[0], p[1]});
        int ans = INT_MAX;
        for (int i = 0; i < points.size(); ++i) {
            for (int j = i+1; j < points.size(); ++j) {
                int x1 = points[i][0], y1 = points[i][1];
                int x2 = points[j][0], y2 = points[j][1];
                if (x1 != x2 && y1 != y2) {
                    if (st.count({x1, y2}) && st.count({x2, y1})) {
                        ans = min(ans, abs(x1-x2)*abs(y1-y2));
                    }
                }
            }
        }
        return ans == INT_MAX ? 0 : ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func minAreaRect(points [][]int) int {
    st := map[[2]int]struct{}{}
    for _, p := range points {
        st[[2]int{p[0], p[1]}] = struct{}{}
    }
    ans := 1 << 30
    for i := 0; i < len(points); i++ {
        for j := i+1; j < len(points); j++ {
            x1, y1 := points[i][0], points[i][1]
            x2, y2 := points[j][0], points[j][1]
            if x1 != x2 && y1 != y2 {
                if _, ok1 := st[[2]int{x1, y2}]; ok1 {
                    if _, ok2 := st[[2]int{x2, y1}]; ok2 {
                        area := abs(x1-x2) * abs(y1-y2)
                        if area < ans { ans = area }
                    }
                }
            }
        }
    }
    if ans == 1<<30 { return 0 }
    return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int minAreaRect(int[][] points) {
        Set<String> st = new HashSet<>();
        for (int[] p : points) st.add(p[0] + "," + p[1]);
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < points.length; ++i) {
            for (int j = i+1; j < points.length; ++j) {
                int x1 = points[i][0], y1 = points[i][1];
                int x2 = points[j][0], y2 = points[j][1];
                if (x1 != x2 && y1 != y2) {
                    if (st.contains(x1+","+y2) && st.contains(x2+","+y1)) {
                        ans = Math.min(ans, Math.abs(x1-x2)*Math.abs(y1-y2));
                    }
                }
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun minAreaRect(points: Array<IntArray>): Int {
        val st = mutableSetOf<Pair<Int,Int>>()
        for (p in points) st.add(p[0] to p[1])
        var ans = Int.MAX_VALUE
        for (i in points.indices) {
            for (j in i+1 until points.size) {
                val (x1, y1) = points[i]
                val (x2, y2) = points[j]
                if (x1 != x2 && y1 != y2) {
                    if ((x1 to y2) in st && (x2 to y1) in st) {
                        ans = minOf(ans, kotlin.math.abs(x1-x2)*kotlin.math.abs(y1-y2))
                    }
                }
            }
        }
        return if (ans == Int.MAX_VALUE) 0 else ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def min_area_rect(points: list[list[int]]) -> int:
    st = set((x, y) for x, y in points)
    ans = float('inf')
    for i in range(len(points)):
        for j in range(i+1, len(points)):
            x1, y1 = points[i]
            x2, y2 = points[j]
            if x1 != x2 and y1 != y2:
                if (x1, y2) in st and (x2, y1) in st:
                    area = abs(x1-x2) * abs(y1-y2)
                    ans = min(ans, area)
    return 0 if ans == float('inf') else ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn min_area_rect(points: Vec<Vec<i32>>) -> i32 {
        use std::collections::HashSet;
        let st: HashSet<(i32,i32)> = points.iter().map(|p| (p[0], p[1])).collect();
        let mut ans = i32::MAX;
        for i in 0..points.len() {
            for j in i+1..points.len() {
                let (x1, y1) = (points[i][0], points[i][1]);
                let (x2, y2) = (points[j][0], points[j][1]);
                if x1 != x2 && y1 != y2 {
                    if st.contains(&(x1, y2)) && st.contains(&(x2, y1)) {
                        let area = (x1-x2).abs() * (y1-y2).abs();
                        ans = ans.min(area);
                    }
                }
            }
        }
        if ans == i32::MAX { 0 } else { ans }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    minAreaRect(points: number[][]): number {
        const st = new Set(points.map(([x, y]) => `${x},${y}`));
        let ans = Number.MAX_SAFE_INTEGER;
        for (let i = 0; i < points.length; ++i) {
            for (let j = i+1; j < points.length; ++j) {
                const [x1, y1] = points[i];
                const [x2, y2] = points[j];
                if (x1 !== x2 && y1 !== y2) {
                    if (st.has(`${x1},${y2}`) && st.has(`${x2},${y1}`)) {
                        const area = Math.abs(x1-x2) * Math.abs(y1-y2);
                        ans = Math.min(ans, area);
                    }
                }
            }
        }
        return ans === Number.MAX_SAFE_INTEGER ? 0 : ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2)
    • Checking all pairs of points.
  • 🧺 Space complexity: O(n)
    • For storing points in a set.