Maximum Area Rectangle With Point Constraints I solution and explanation
Google
3 more videos on this problem
3380. Maximum Area Rectangle With Point Constraints I | Array | Sorting | MathAryan Mittal · 11:28 · 2K views
3380. Maximum Area Rectangle With Point Constraints I (Leetcode Medium)Programming Live with Larry · 9:50 · 486 views
Maximum Area Rectangle With Point Constraints I | LeetCode Weekly Contest 427 |Java| Developer CoderDeveloper Coder · 11:38 · 395 views
Maximum Area Rectangle With Point Constraints I | Day 9 of #30DaysofCode Challenge with EducativeThe Runtime Diaries · 13:28 · 49 views
The 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:
Input: points = [[1,1],[1,3],[3,1],[3,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: points = [[1,1],[1,3],[3,1],[3,3],[2,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: points = [[1,1],[1,3],[3,1],[3,3],[1,2],[3,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 <= points.length <= 10points[i].length == 20 <= xi, yi <= 100- All the given points are unique.
Approach overview
Problem Overview: You are given a list of 2D points on a plane. The task is to find the maximum area of an axis-aligned rectangle whose four corners exist in the input and that does not contain any additional points inside or on its edges. If no valid rectangle exists, return 0.
Approach 1: Brute Force Corner Enumeration (O(n^4) time, O(1) space)
Check every combination of four points and determine whether they form an axis-aligned rectangle. For a valid rectangle, two points must share the same x-coordinate (left/right edges) and two must share the same y-coordinate (top/bottom edges). After identifying a rectangle candidate, iterate through all points again to ensure no other point lies inside or on the rectangle boundary except the four corners. This approach is straightforward but extremely slow because it evaluates every 4-point combination.
Approach 2: Diagonal Enumeration with Point Set (O(n^3) time, O(n) space)
Instead of choosing four corners directly, treat pairs of points as potential diagonally opposite corners. For two points (x1, y1) and (x2, y2) where x1 != x2 and y1 != y2, the other two rectangle corners must be (x1, y2) and (x2, y1). Store all points in a hash set for O(1) membership checks and verify that these two complementary corners exist. Once all four corners are confirmed, scan the points to ensure no extra point lies within the rectangle or along its edges. Compute the area using abs(x1 - x2) * abs(y1 - y2) and keep the maximum. This enumeration significantly reduces combinations compared to brute force while remaining simple to implement.
Sorting the points by coordinates can help with deterministic iteration and pruning, though the core idea relies on fast lookups in a set. The approach mainly involves coordinate comparisons and membership checks, making it a natural application of geometry reasoning combined with array traversal and optional sorting.
Recommended for interviews: Diagonal enumeration with a hash set. Interviewers expect you to recognize that a rectangle can be uniquely determined by its diagonal corners. The brute force version shows the baseline idea, but the diagonal enumeration demonstrates better algorithmic thinking and reduces the search space from O(n^4) to O(n^3).
Solution
We can enumerate the bottom-left corner (x_3, y_3) and the top-right corner (x_4, y_4) of the rectangle. Then, we enumerate all points (x, y) and check if the point is inside or on the boundary of the rectangle. If it is, it does not meet the condition. Otherwise, we exclude the points outside the rectangle and check if there are 4 remaining points. If there are, these 4 points can form a rectangle. We calculate the area of the rectangle and take the maximum value.
The time complexity is O(n^3), where n is the length of the array points. The space complexity is O(1).
class Solution:
def maxRectangleArea(self, points: List[List[int]]) -> int:
def check(x1: int, y1: int, x2: int, y2: int) -> bool:
cnt = 0
for x, y in points:
if x < x1 or x > x2 or y < y1 or y > y2:
continue
if (x == x1 or x == x2) and (y == y1 or y == y2):
cnt += 1
continue
return False
return cnt == 4
ans = -1
for i, (x1, y1) in enumerate(points):
for x2, y2 in points[:i]:
x3, y3 = min(x1, x2), min(y1, y2)
x4, y4 = max(x1, x2), max(y1, y2)
if check(x3, y3, x4, y4):
ans = max(ans, (x4 - x3) * (y4 - y3))
return ansclass Solution {
public int maxRectangleArea(int[][] points) {
int ans = -1;
for (int i = 0; i < points.length; ++i) {
int x1 = points[i][0], y1 = points[i][1];
for (int j = 0; j < i; ++j) {
int x2 = points[j][0], y2 = points[j][1];
int x3 = Math.min(x1, x2), y3 = Math.min(y1, y2);
int x4 = Math.max(x1, x2), y4 = Math.max(y1, y2);
if (check(points, x3, y3, x4, y4)) {
ans = Math.max(ans, (x4 - x3) * (y4 - y3));
}
}
}
return ans;
}
private boolean check(int[][] points, int x1, int y1, int x2, int y2) {
int cnt = 0;
for (var p : points) {
int x = p[0];
int y = p[1];
if (x < x1 || x > x2 || y < y1 || y > y2) {
continue;
}
if ((x == x1 || x == x2) && (y == y1 || y == y2)) {
cnt++;
continue;
}
return false;
}
return cnt == 4;
}
}class Solution {
public:
int maxRectangleArea(vector<vector<int>>& points) {
auto check = [&](int x1, int y1, int x2, int y2) -> bool {
int cnt = 0;
for (const auto& point : points) {
int x = point[0];
int y = point[1];
if (x < x1 || x > x2 || y < y1 || y > y2) {
continue;
}
if ((x == x1 || x == x2) && (y == y1 || y == y2)) {
cnt++;
continue;
}
return false;
}
return cnt == 4;
};
int ans = -1;
for (int i = 0; i < points.size(); i++) {
int x1 = points[i][0], y1 = points[i][1];
for (int j = 0; j < i; j++) {
int x2 = points[j][0], y2 = points[j][1];
int x3 = min(x1, x2), y3 = min(y1, y2);
int x4 = max(x1, x2), y4 = max(y1, y2);
if (check(x3, y3, x4, y4)) {
ans = max(ans, (x4 - x3) * (y4 - y3));
}
}
}
return ans;
}
};function maxRectangleArea(points: number[][]): number {
const check = (x1: number, y1: number, x2: number, y2: number): boolean => {
let cnt = 0;
for (const point of points) {
const [x, y] = point;
if (x < x1 || x > x2 || y < y1 || y > y2) {
continue;
}
if ((x === x1 || x === x2) && (y === y1 || y === y2)) {
cnt++;
continue;
}
return false;
}
return cnt === 4;
};
let ans = -1;
for (let i = 0; i < points.length; i++) {
const [x1, y1] = points[i];
for (let j = 0; j < i; j++) {
const [x2, y2] = points[j];
const [x3, y3] = [Math.min(x1, x2), Math.min(y1, y2)];
const [x4, y4] = [Math.max(x1, x2), Math.max(y1, y2)];
if (check(x3, y3, x4, y4)) {
ans = Math.max(ans, (x4 - x3) * (y4 - y3));
}
}
}
return ans;
}func maxRectangleArea(points [][]int) int {
check := func(x1, y1, x2, y2 int) bool {
cnt := 0
for _, point := range points {
x, y := point[0], point[1]
if x < x1 || x > x2 || y < y1 || y > y2 {
continue
}
if (x == x1 || x == x2) && (y == y1 || y == y2) {
cnt++
continue
}
return false
}
return cnt == 4
}
ans := -1
for i := 0; i < len(points); i++ {
x1, y1 := points[i][0], points[i][1]
for j := 0; j < i; j++ {
x2, y2 := points[j][0], points[j][1]
x3, y3 := min(x1, x2), min(y1, y2)
x4, y4 := max(x1, x2), max(y1, y2)
if check(x3, y3, x4, y4) {
ans = max(ans, (x4-x3)*(y4-y3))
}
}
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force 4-Point Enumeration | O(n^4) | O(1) | Conceptual baseline or very small input sizes |
| Diagonal Enumeration with Hash Set | O(n^3) | O(n) | General solution used in interviews and competitive programming |
Frequently asked questions
Is Maximum Area Rectangle With Point Constraints I easy or hard?
Maximum Area Rectangle With Point Constraints I is generally classified as a medium difficulty problem. The geometric observation about diagonal corners is straightforward, but correctly validating that no extra points lie inside the rectangle requires careful implementation.
Maximum Area Rectangle With Point Constraints I Python/Java solution
The typical implementation enumerates pairs of points as diagonals, checks if the other two corners exist in a hash set, and verifies that no additional point lies inside the rectangle. This logic translates directly across Python, Java, C++, Go, and TypeScript with O(n^3) time complexity.
How to solve Maximum Area Rectangle With Point Constraints I in O(n)?
An O(n) solution is not practical because rectangles depend on relationships between multiple point pairs. The typical approach enumerates diagonal pairs and validates the rectangle, leading to O(n^3) complexity. More advanced geometric data structures like segment trees or Binary Indexed Trees may reduce checks in extended variants but are not required for the basic version.
What is the best approach for Maximum Area Rectangle With Point Constraints I?
The most practical approach is diagonal enumeration with a hash set. Treat two points as potential opposite corners of a rectangle and compute the other two corners directly. Use a set to check if those points exist and scan the input to confirm no extra points lie inside the rectangle. This reduces the search space to O(n^3) time with O(n) space.
Is Maximum Area Rectangle With Point Constraints I asked at Google/Amazon/Meta?
Geometry and coordinate-based enumeration problems similar to this appear in interviews at companies like Google, Amazon, and Meta. The exact problem may vary, but the pattern of validating rectangles using coordinate relationships and hash lookups is common in technical interviews.
What data structure is used in Maximum Area Rectangle With Point Constraints I?
A hash set is typically used to store all points for constant-time coordinate lookup. The algorithm also relies on simple geometry checks and nested iteration over the array of points to test possible rectangle diagonals.
What is the time complexity of Maximum Area Rectangle With Point Constraints I?
The common optimized enumeration approach runs in O(n^3) time and O(n) space. Two points are selected as diagonal corners, the other two corners are checked using a hash set, and the remaining points are scanned to ensure the rectangle contains no extra points.