Problem

There are n points on an infinite plane. You are given two integer arrays xCoord and yCoord where (xCoord[i], yCoord[i]) represents the coordinates of the ith point.

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:ord = [1,1,3,3], yCoord = [1,3,1,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:ord = [1,1,3,3,2], yCoord = [1,3,1,3,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:ord = [1,1,3,3,1,3], yCoord = [1,3,1,3,2,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 <= xCoord.length == yCoord.length <= 2 * 10^5
  • 0 <= xCoord[i], yCoord[i] <= 8 * 10^7
  • All the given points are unique.

Examples

Solution

Method 1 – Brute Force with Set Lookup

Intuition

This problem is similar to the first version, but the input is given as two separate arrays for x and y coordinates. We can use the same approach: for each pair of points, treat them as opposite corners, check if the other two corners exist, and ensure no other point is inside or on the border.

Approach

  1. Combine xCoord and yCoord into a list of points and store them 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
29
30

class Solution {
public:
    int maxAreaRect(vector<int>& xCoord, vector<int>& yCoord) {
        int n = xCoord.size();
        set<pair<int,int>> s;
        for (int i = 0; i < n; ++i) s.insert({xCoord[i], yCoord[i]});
        int ans = -1;
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                int x1 = xCoord[i], y1 = yCoord[i];
                int x2 = xCoord[j], y2 = yCoord[j];
                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 (int k = 0; k < n; ++k) {
                        int px = xCoord[k], py = yCoord[k];
                        if (px > minx && px < maxx && py > 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
31
32
33
34
35
36
37
38
39
40
41

func maxAreaRect(xCoord, yCoord []int) int {
    n := len(xCoord)
    s := map[[2]int]struct{}{}
    for i := 0; i < n; i++ {
        s[[2]int{xCoord[i], yCoord[i]}] = struct{}{}
    }
    ans := -1
    for i := 0; i < n; i++ {
        for j := i+1; j < n; j++ {
            x1, y1 := xCoord[i], yCoord[i]
            x2, y2 := xCoord[j], yCoord[j]
            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 k := 0; k < n; k++ {
                        px, py := xCoord[k], yCoord[k]
                        if px > minx && px < maxx && py > miny && py < 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
28
29

class Solution {
    public int maxAreaRect(int[] xCoord, int[] yCoord) {
        int n = xCoord.length;
        Set<String> s = new HashSet<>();
        for (int i = 0; i < n; i++) s.add(xCoord[i] + "," + yCoord[i]);
        int ans = -1;
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                int x1 = xCoord[i], y1 = yCoord[i];
                int x2 = xCoord[j], y2 = yCoord[j];
                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 k = 0; k < n; k++) {
                        int px = xCoord[k], py = yCoord[k];
                        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;
    }
}
 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

class Solution {
    fun maxAreaRect(xCoord: IntArray, yCoord: IntArray): Int {
        val n = xCoord.size
        val s = mutableSetOf<Pair<Int,Int>>()
        for (i in 0 until n) s.add(Pair(xCoord[i], yCoord[i]))
        var ans = -1
        for (i in 0 until n) {
            for (j in i+1 until n) {
                val x1 = xCoord[i]; val y1 = yCoord[i]
                val x2 = xCoord[j]; val y2 = yCoord[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 (k in 0 until n) {
                        val px = xCoord[k]; val py = yCoord[k]
                        if (px > minx && px < maxx && py > miny && py < 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
23

class Solution:
    def maxAreaRect(self, xCoord: list[int], yCoord: list[int]) -> int:
        n = len(xCoord)
        s = set(zip(xCoord, yCoord))
        ans = -1
        for i in range(n):
            for j in range(i+1, n):
                x1, y1 = xCoord[i], yCoord[i]
                x2, y2 = xCoord[j], yCoord[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 k in range(n):
                        px, py = xCoord[k], yCoord[k]
                        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
31

impl Solution {
    pub fn max_area_rect(x_coord: Vec<i32>, y_coord: Vec<i32>) -> i32 {
        use std::collections::HashSet;
        let n = x_coord.len();
        let s: HashSet<(i32,i32)> = (0..n).map(|i| (x_coord[i], y_coord[i])).collect();
        let mut ans = -1;
        for i in 0..n {
            for j in i+1..n {
                let (x1, y1) = (x_coord[i], y_coord[i]);
                let (x2, y2) = (x_coord[j], y_coord[j]);
                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 k in 0..n {
                        let (px, py) = (x_coord[k], y_coord[k]);
                        if px > minx && px < maxx && py > miny && py < 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
26
27
28

class Solution {
    maxAreaRect(xCoord: number[], yCoord: number[]): number {
        const n = xCoord.length;
        const s = new Set(xCoord.map((x, i) => `${x},${yCoord[i]}`));
        let ans = -1;
        for (let i = 0; i < n; ++i) {
            for (let j = i+1; j < n; ++j) {
                const x1 = xCoord[i], y1 = yCoord[i];
                const x2 = xCoord[j], y2 = yCoord[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 (let k = 0; k < n; ++k) {
                        const px = xCoord[k], py = yCoord[k];
                        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.