Maximum Area Rectangle With Point Constraints II
HardUpdated: Aug 2, 2025
Practice on:
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.
Examples
Example 1
Input:ord = [1,1,3,3], yCoord = [1,3,1,3]
Output: 4
Explanation:
****
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:ord = [1,1,3,3,2], yCoord = [1,3,1,3,2]
Output: -1
Explanation:
****
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:ord = [1,1,3,3,1,3], yCoord = [1,3,1,3,2,2]
Output: 2
Explanation:
****
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^50 <= xCoord[i], yCoord[i] <= 8 * 10^7- All the given points are unique.
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
- Combine xCoord and yCoord into a list of points and store them in a set for O(1) lookup.
- For each pair of points (p1, p2) with different x and y, treat them as opposite corners.
- Check if the other two corners exist in the set.
- For each rectangle, check that no other point is inside or on the border except the four corners.
- Track the maximum area found.
- Return the maximum area or -1 if none found.
Code
C++
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;
}
};
Go
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 }
Java
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;
}
}
Kotlin
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
}
}
Python
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
Rust
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
}
}
TypeScript
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.