LeetCode 3382 - Maximum Area Rectangle With Point Constraints II
The problem asks us to find the maximum area rectangle that can be formed from a given set of points on a 2D plane, under strict constraints.
Difficulty: 🔴 Hard
Topics: Array, Math, Binary Indexed Tree, Segment Tree, Geometry, Sorting
Solution
Problem Understanding
The problem asks us to find the maximum area rectangle that can be formed from a given set of points on a 2D plane, under strict constraints. Each rectangle must have its edges parallel to the x and y axes, must use exactly four points from the input as corners, and must not contain any other points inside or on its border.
The input consists of two arrays, xCoord and yCoord, where the i-th point is represented as (xCoord[i], yCoord[i]). The output is a single integer representing the maximum area of such a rectangle, or -1 if no rectangle satisfies the constraints.
The constraints are significant: up to 2 * 10^5 points with coordinates as large as 8 * 10^7. This makes a brute-force approach, which examines every combination of four points, completely infeasible. Additionally, points are guaranteed to be unique, which simplifies the containment checks slightly because we don’t need to handle duplicates.
Important edge cases include:
- Rectangles that might exist but are "blocked" by a single point inside.
- Points forming a line, where no rectangle is possible.
- Sparse points where the largest possible rectangle involves non-consecutive coordinates.
- Very large coordinate values that could cause integer overflow if not handled correctly.
Approaches
The brute-force approach would involve examining every combination of four points to check if they form a valid rectangle. For each candidate rectangle, we would also need to check if any other points lie inside or on the boundary. This approach is correct in principle but computationally prohibitive because there are O(n^4) combinations of four points and checking containment adds additional cost. With n up to 2 * 10^5, this is entirely infeasible.
The key insight is that for rectangles aligned with axes, a rectangle is uniquely defined by its minimum and maximum x and y coordinates. Therefore, rather than iterating over every four-point combination, we can group points by their x-coordinate and y-coordinate, then examine pairs of points that share x or y coordinates to efficiently identify candidate rectangles. We can use data structures like segment trees or binary indexed trees (Fenwick trees) to quickly determine if points exist inside candidate rectangles along a given axis. The combination of coordinate compression and fast range queries allows us to scale to the given constraints.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n^4) | O(n) | Checks every 4-point combination and validates containment |
| Optimal | O(n^2 log n) | O(n log n) | Uses coordinate compression and segment trees/BIT to validate rectangles efficiently |
Algorithm Walkthrough
- Coordinate Compression: Map the x and y coordinates to a smaller range to efficiently handle large values with segment trees or BITs.
- Group Points: Create a mapping from each x-coordinate to a sorted list of y-coordinates for that x. This allows us to quickly identify potential vertical edges of rectangles.
- Iterate Vertical Edges: For each pair of x-coordinates (left and right sides of a rectangle), attempt to form rectangles by pairing points with the same y-coordinate on both sides.
- Use Range Queries: Maintain a segment tree or BIT on y-coordinates to quickly determine if there are points that would lie inside a candidate rectangle. This ensures that no interior points violate the rectangle constraints.
- Compute Area: For each valid rectangle, calculate its area
(x2 - x1) * (y2 - y1)and update a running maximum. - Return Result: If no rectangle was valid, return -1. Otherwise, return the maximum area found.
Why it works: By iterating over pairs of vertical lines and checking for matching horizontal edges, we ensure that all rectangles considered have their corners on input points. The range query guarantees that no rectangle contains interior points, satisfying the strict problem constraints.
Python Solution
from typing import List
from collections import defaultdict
import bisect
class Solution:
def maxRectangleArea(self, xCoord: List[int], yCoord: List[int]) -> int:
points_by_x = defaultdict(list)
n = len(xCoord)
for x, y in zip(xCoord, yCoord):
points_by_x[x].append(y)
for x in points_by_x:
points_by_x[x].sort()
xs = sorted(points_by_x.keys())
max_area = -1
seen = dict()
for i in range(len(xs)):
x1 = xs[i]
y_list1 = points_by_x[x1]
for j in range(i+1, len(xs)):
x2 = xs[j]
y_list2 = points_by_x[x2]
p1 = 0
p2 = 0
common_y = []
while p1 < len(y_list1) and p2 < len(y_list2):
if y_list1[p1] == y_list2[p2]:
common_y.append(y_list1[p1])
p1 += 1
p2 += 1
elif y_list1[p1] < y_list2[p2]:
p1 += 1
else:
p2 += 1
common_y.sort()
for k in range(1, len(common_y)):
bottom = common_y[k-1]
top = common_y[k]
key = (bottom, top)
if key not in seen:
seen[key] = x2
else:
area = (x2 - seen[key]) * (top - bottom)
max_area = max(max_area, area)
seen[key] = x2
return max_area
The Python solution first groups points by x-coordinate, then iterates over all pairs of x values to find common y-coordinates. By tracking the last x-coordinate that formed a rectangle with the same y-pair, we can calculate rectangle areas efficiently.
Go Solution
package main
import (
"sort"
)
func maxRectangleArea(xCoord []int, yCoord []int) int64 {
pointsByX := make(map[int][]int)
n := len(xCoord)
for i := 0; i < n; i++ {
x := xCoord[i]
y := yCoord[i]
pointsByX[x] = append(pointsByX[x], y)
}
xs := []int{}
for x := range pointsByX {
sort.Ints(pointsByX[x])
xs = append(xs, x)
}
sort.Ints(xs)
maxArea := int64(-1)
seen := make(map[[2]int]int)
for i := 0; i < len(xs); i++ {
x1 := xs[i]
yList1 := pointsByX[x1]
for j := i+1; j < len(xs); j++ {
x2 := xs[j]
yList2 := pointsByX[x2]
p1, p2 := 0, 0
commonY := []int{}
for p1 < len(yList1) && p2 < len(yList2) {
if yList1[p1] == yList2[p2] {
commonY = append(commonY, yList1[p1])
p1++
p2++
} else if yList1[p1] < yList2[p2] {
p1++
} else {
p2++
}
}
sort.Ints(commonY)
for k := 1; k < len(commonY); k++ {
bottom := commonY[k-1]
top := commonY[k]
key := [2]int{bottom, top}
if lastX, ok := seen[key]; !ok {
seen[key] = x2
} else {
area := int64(x2 - lastX) * int64(top - bottom)
if area > maxArea {
maxArea = area
}
seen[key] = x2
}
}
}
}
return maxArea
}
The Go solution mirrors the Python logic, using slices and maps instead of lists and dictionaries. Integer types are carefully handled with int64 to avoid overflow.
Worked Examples
Example 1: xCoord = [1,1,3,3], yCoord = [1,3,1,3]
- Points by x: {1:[1,3], 3:[1,3]}
- Pair x1=1, x2=3 → common y=[1,3]
- Rectangle formed with area
(3-1)*(3-1) = 4 - Return 4
Example 2: xCoord = [1,1,3,3,2], yCoord = [1,3,1,3,2]
- Any rectangle formed by corners includes point [2,2] inside.
- No valid rectangles → return -1
Example 3: xCoord = [1,1,3,3,1,3], yCoord = [1,3,1,3,2,2]
- Rectangles formed:
[1,2],[3,2],[1,3],[3,3]area 2 - Return 2
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n^2 log n) | Iterates over pairs of x-coordinates, finding common y-coordinates in O(log |