3681. Maximum Area Rectangle With Point Constraints I
My accepted Python solution to LeetCode problem 3681, Maximum Area Rectangle With Point Constraints I, running in 98ms.
- Difficulty: Medium
- Python
- Runtime 98ms
- Memory 17.3MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 98ms, memory 17.3MB, accepted 2025-12-31.
class Solution:
def maxRectangleArea(self, points: List[List[int]]) -> int:
from itertools import combinations
point_set = set(tuple(p) for p in points)
n = len(points)
max_area = -1
# Try all combinations of 4 points
for combo in combinations(range(n), 4):
pts = [points[i] for i in combo]
# Check if they form a valid rectangle with sides parallel to axes
xs = sorted(set(p[0] for p in pts))
ys = sorted(set(p[1] for p in pts))
if len(xs) != 2 or len(ys) != 2:
continue
# Check all 4 corners exist
corners = {(xs[0], ys[0]), (xs[0], ys[1]), (xs[1], ys[0]), (xs[1], ys[1])}
if set(tuple(p) for p in pts) != corners:
continue
# Check no other point lies inside or on the border
valid = True
for p in points:
px, py = p
if (px, py) in corners:
continue
# Check if point is inside or on border
if xs[0] <= px <= xs[1] and ys[0] <= py <= ys[1]:
valid = False
break
if valid:
area = (xs[1] - xs[0]) * (ys[1] - ys[0])
max_area = max(max_area, area)
return max_area