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

1
2
3
4
5
6
7
8

Input: points = [[1,1],[1,3],[3,1],[3,3]]
Output: 4
Explanation:
**![Example 1
diagram](https://assets.leetcode.com/uploads/2024/11/02/example1.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

1
2
3
4
5
6
7

Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output:**** -1
Explanation:
**![Example 2
diagram](https://assets.leetcode.com/uploads/2024/11/02/example2.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

1
2
3
4
5
6
7
8

Input: points = [[1,1],[1,3],[3,1],[3,3],[1,2],[3,2]]
Output: 2
Explanation:
**![Example 3
diagram](https://assets.leetcode.com/uploads/2024/11/02/example3.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.

Examples

Solution

Method 1 – Brute Force with Set Lookup

Intuition

To form a rectangle with axis-aligned edges, we need two pairs of points with the same x and two with the same y. For each pair of points that could be opposite corners, check if the other two corners exist. To ensure no other point is inside or on the border, check all points are strictly outside the rectangle.

Approach

  1. Store all points in a set for O(1) lookup.
  2. For each pair of points (p1, p2) with different x and y, treat them as opposite corners.
  3. Check if the other two corners exist in the set.
  4. For each rectangle, check that no other point is inside or on the border except the four corners.
  5. Track the maximum area found.
  6. Return the maximum area or -1 if none found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    int maxAreaRect(vector<vector<int>>& points) {
        set<pair<int,int>> s;
        for (auto& p : points) s.insert({p[0], p[1]});
        int ans = -1, n = points.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                int x1 = points[i][0], y1 = points[i][1];
                int x2 = points[j][0], y2 = points[j][1];
                if (x1 == x2 || y1 == y2) continue;
                if (s.count({x1, y2}) && s.count({x2, y1})) {
                    int minx = min(x1, x2), maxx = max(x1, x2);
                    int miny = min(y1, y2), maxy = max(y1, y2);
                    bool valid = true;
                    for (auto& p : points) {
                        if (p[0] > minx && p[0] < maxx && p[1] > miny && p[1] < maxy) {
                            valid = false;
                            break;
                        }
                    }
                    if (valid) ans = max(ans, abs(x1-x2)*abs(y1-y2));
                }
            }
        }
        return 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

func maxAreaRect(points [][]int) int {
    s := map[[2]int]struct{}{}
    for _, p := range points {
        s[[2]int{p[0], p[1]}] = struct{}{}
    }
    ans := -1
    n := len(points)
    for i := 0; i < n; i++ {
        for j := i+1; j < n; j++ {
            x1, y1 := points[i][0], points[i][1]
            x2, y2 := points[j][0], points[j][1]
            if x1 == x2 || y1 == y2 {
                continue
            }
            if _, ok := s[[2]int{x1, y2}]; ok {
                if _, ok2 := s[[2]int{x2, y1}]; ok2 {
                    minx, maxx := min(x1, x2), max(x1, x2)
                    miny, maxy := min(y1, y2), max(y1, y2)
                    valid := true
                    for _, p := range points {
                        if p[0] > minx && p[0] < maxx && p[1] > miny && p[1] < maxy {
                            valid = false
                            break
                        }
                    }
                    if valid {
                        area := abs(x1-x2) * abs(y1-y2)
                        if area > ans {
                            ans = area
                        }
                    }
                }
            }
        }
    }
    return ans
}
func min(a, b int) int { if a < b { return a }; return b }
func max(a, b int) int { if a > b { return a }; return b }
func abs(a int) int { if a < 0 { return -a }; return a }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    public int maxAreaRect(int[][] points) {
        Set<String> s = new HashSet<>();
        for (int[] p : points) s.add(p[0] + "," + p[1]);
        int ans = -1, n = points.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                int x1 = points[i][0], y1 = points[i][1];
                int x2 = points[j][0], y2 = points[j][1];
                if (x1 == x2 || y1 == y2) continue;
                if (s.contains(x1+","+y2) && s.contains(x2+","+y1)) {
                    int minx = Math.min(x1, x2), maxx = Math.max(x1, x2);
                    int miny = Math.min(y1, y2), maxy = Math.max(y1, y2);
                    boolean valid = true;
                    for (int[] p : points) {
                        if (p[0] > minx && p[0] < maxx && p[1] > miny && p[1] < maxy) {
                            valid = false;
                            break;
                        }
                    }
                    if (valid) ans = Math.max(ans, Math.abs(x1-x2)*Math.abs(y1-y2));
                }
            }
        }
        return 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
25
26
27
28
29
30

class Solution {
    fun maxAreaRect(points: Array<IntArray>): Int {
        val s = mutableSetOf<Pair<Int,Int>>()
        for (p in points) s.add(Pair(p[0], p[1]))
        var ans = -1
        val n = points.size
        for (i in 0 until n) {
            for (j in i+1 until n) {
                val (x1, y1) = points[i]
                val (x2, y2) = points[j]
                if (x1 == x2 || y1 == y2) continue
                if (Pair(x1, y2) in s && Pair(x2, y1) in s) {
                    val minx = minOf(x1, x2)
                    val maxx = maxOf(x1, x2)
                    val miny = minOf(y1, y2)
                    val maxy = maxOf(y1, y2)
                    var valid = true
                    for (p in points) {
                        if (p[0] > minx && p[0] < maxx && p[1] > miny && p[1] < maxy) {
                            valid = false
                            break
                        }
                    }
                    if (valid) ans = maxOf(ans, kotlin.math.abs(x1-x2)*kotlin.math.abs(y1-y2))
                }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def maxAreaRect(self, points: list[list[int]]) -> int:
        s = set(map(tuple, points))
        ans = -1
        n = len(points)
        for i in range(n):
            for j in range(i+1, n):
                x1, y1 = points[i]
                x2, y2 = points[j]
                if x1 == x2 or y1 == y2:
                    continue
                if (x1, y2) in s and (x2, y1) in s:
                    minx, maxx = min(x1, x2), max(x1, x2)
                    miny, maxy = min(y1, y2), max(y1, y2)
                    valid = True
                    for px, py in points:
                        if minx < px < maxx and miny < py < maxy:
                            valid = False
                            break
                    if valid:
                        ans = max(ans, abs(x1-x2)*abs(y1-y2))
        return 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
25
26
27
28
29
30

impl Solution {
    pub fn max_area_rect(points: Vec<Vec<i32>>) -> i32 {
        use std::collections::HashSet;
        let s: HashSet<(i32,i32)> = points.iter().map(|p| (p[0],p[1])).collect();
        let mut ans = -1;
        let n = points.len();
        for i in 0..n {
            for j in i+1..n {
                let (x1, y1) = (points[i][0], points[i][1]);
                let (x2, y2) = (points[j][0], points[j][1]);
                if x1 == x2 || y1 == y2 { continue; }
                if s.contains(&(x1, y2)) && s.contains(&(x2, y1)) {
                    let (minx, maxx) = (x1.min(x2), x1.max(x2));
                    let (miny, maxy) = (y1.min(y2), y1.max(y2));
                    let mut valid = true;
                    for p in &points {
                        if p[0] > minx && p[0] < maxx && p[1] > miny && p[1] < maxy {
                            valid = false;
                            break;
                        }
                    }
                    if valid {
                        ans = ans.max((x1-x2).abs()*(y1-y2).abs());
                    }
                }
            }
        }
        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
25

class Solution {
    maxAreaRect(points: number[][]): number {
        const s = new Set(points.map(p => p.join(",")));
        let ans = -1, n = points.length;
        for (let i = 0; i < n; ++i) {
            for (let j = i+1; j < n; ++j) {
                const [x1, y1] = points[i], [x2, y2] = points[j];
                if (x1 === x2 || y1 === y2) continue;
                if (s.has(`${x1},${y2}`) && s.has(`${x2},${y1}`)) {
                    const minx = Math.min(x1, x2), maxx = Math.max(x1, x2);
                    const miny = Math.min(y1, y2), maxy = Math.max(y1, y2);
                    let valid = true;
                    for (const [px, py] of points) {
                        if (px > minx && px < maxx && py > miny && py < maxy) {
                            valid = false;
                            break;
                        }
                    }
                    if (valid) ans = Math.max(ans, Math.abs(x1-x2)*Math.abs(y1-y2));
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^3), since for each pair of points, we may check all points for validity.
  • 🧺 Space complexity: O(n), for the set of points.