Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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:
Return the maximum area that you can obtain or -1 if no such rectangle is possible.
Example 1:
Input: xCoord = [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: xCoord = [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: xCoord = [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 * 1050 <= xCoord[i], yCoord[i] <= 8 * 107Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Math · Segment Tree
[1,1,3,3] [1,3,1,3]
[1,1,3,3,2] [1,3,1,3,2]
[1,1,3,3,1,3] [1,3,1,3,2,2]
minimum-area-rectangle)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3382: Maximum Area Rectangle With Point Constraints II
// Auto-generated Java example from go.
class Solution {
public void exampleSolution() {
}
}
// Reference (go):
// // Accepted solution for LeetCode #3382: Maximum Area Rectangle With Point Constraints II
// package main
//
// import (
// "cmp"
// "slices"
// "sort"
// )
//
// // https://space.bilibili.com/206214
// type fenwick []int
//
// func (f fenwick) add(i int) {
// for ; i < len(f); i += i & -i {
// f[i]++
// }
// }
//
// func (f fenwick) pre(i int) (res int) {
// for ; i > 0; i &= i - 1 {
// res += f[i]
// }
// return
// }
//
// func (f fenwick) query(l, r int) int {
// return f.pre(r) - f.pre(l-1)
// }
//
// func maxRectangleArea(xCoord, ys []int) int64 {
// type pair struct{ x, y int }
// points := make([]pair, len(xCoord))
// for i := range xCoord {
// points[i] = pair{xCoord[i], ys[i]}
// }
// slices.SortFunc(points, func(a, b pair) int { return cmp.Or(a.x-b.x, a.y-b.y) })
//
// // 离散化用
// slices.Sort(ys)
// ys = slices.Compact(ys)
//
// ans := -1
// tree := make(fenwick, len(ys)+1)
// tree.add(sort.SearchInts(ys, points[0].y) + 1) // 离散化
// type tuple struct{ x, y, c int }
// pre := make([]tuple, len(ys))
// for i := 1; i < len(points); i++ {
// x1, y1 := points[i-1].x, points[i-1].y
// x2, y2 := points[i].x, points[i].y
// y := sort.SearchInts(ys, y2) // 离散化
// tree.add(y + 1)
// if x1 != x2 { // 两点不在同一列
// continue
// }
// cur := tree.query(sort.SearchInts(ys, y1)+1, y+1)
// p := pre[y]
// if p.c > 0 && p.c+2 == cur && p.y == y1 {
// ans = max(ans, (x2-p.x)*(y2-y1))
// }
// pre[y] = tuple{x1, y1, cur}
// }
// return int64(ans)
// }
// Accepted solution for LeetCode #3382: Maximum Area Rectangle With Point Constraints II
package main
import (
"cmp"
"slices"
"sort"
)
// https://space.bilibili.com/206214
type fenwick []int
func (f fenwick) add(i int) {
for ; i < len(f); i += i & -i {
f[i]++
}
}
func (f fenwick) pre(i int) (res int) {
for ; i > 0; i &= i - 1 {
res += f[i]
}
return
}
func (f fenwick) query(l, r int) int {
return f.pre(r) - f.pre(l-1)
}
func maxRectangleArea(xCoord, ys []int) int64 {
type pair struct{ x, y int }
points := make([]pair, len(xCoord))
for i := range xCoord {
points[i] = pair{xCoord[i], ys[i]}
}
slices.SortFunc(points, func(a, b pair) int { return cmp.Or(a.x-b.x, a.y-b.y) })
// 离散化用
slices.Sort(ys)
ys = slices.Compact(ys)
ans := -1
tree := make(fenwick, len(ys)+1)
tree.add(sort.SearchInts(ys, points[0].y) + 1) // 离散化
type tuple struct{ x, y, c int }
pre := make([]tuple, len(ys))
for i := 1; i < len(points); i++ {
x1, y1 := points[i-1].x, points[i-1].y
x2, y2 := points[i].x, points[i].y
y := sort.SearchInts(ys, y2) // 离散化
tree.add(y + 1)
if x1 != x2 { // 两点不在同一列
continue
}
cur := tree.query(sort.SearchInts(ys, y1)+1, y+1)
p := pre[y]
if p.c > 0 && p.c+2 == cur && p.y == y1 {
ans = max(ans, (x2-p.x)*(y2-y1))
}
pre[y] = tuple{x1, y1, cur}
}
return int64(ans)
}
# Accepted solution for LeetCode #3382: Maximum Area Rectangle With Point Constraints II
#
# @lc app=leetcode id=3382 lang=python3
#
# [3382] Maximum Area Rectangle With Point Constraints II
#
# @lc code=start
class Solution:
def maxRectangleArea(self, xCoord: List[int], yCoord: List[int]) -> int:
# Combine coordinates into points
points = sorted(zip(xCoord, yCoord))
n = len(points)
# Coordinate compression for Y
unique_ys = sorted(list(set(yCoord)))
y_map = {y: i for i, y in enumerate(unique_ys)}
m = len(unique_ys)
# Segment Tree for Range Maximum Query
# We store the last seen x-index (from the unique_xs list) for each y-rank.
# Initialize with -1.
tree = [-1] * (4 * m)
def update(node, start, end, idx, val):
if start == end:
tree[node] = val
return
mid = (start + end) // 2
if idx <= mid:
update(2 * node, start, mid, idx, val)
else:
update(2 * node + 1, mid + 1, end, idx, val)
tree[node] = max(tree[2 * node], tree[2 * node + 1])
def query(node, start, end, L, R):
if R < start or end < L:
return -1
if L <= start and end <= R:
return tree[node]
mid = (start + end) // 2
return max(query(2 * node, start, mid, L, R),
query(2 * node + 1, mid + 1, end, L, R))
# Group points by x-coordinate
from collections import defaultdict
points_by_x = defaultdict(list)
for x, y in points:
points_by_x[x].append(y)
# Sort unique x coordinates to iterate in order
sorted_unique_xs = sorted(points_by_x.keys())
# Map to store the last x-coordinate where a specific segment (y1, y2) was seen
# Key: (y1, y2), Value: x_coordinate
# Note: We store the actual x-coordinate value for area calculation,
# but the segment tree stores indices of sorted_unique_xs.
last_seen_segment_x = {}
max_area = -1
for i, x in enumerate(sorted_unique_xs):
ys = points_by_x[x]
# ys is already sorted because we sorted 'points' initially and insertion order is preserved
# or we can explicitly sort to be safe
ys.sort()
# Check segments formed by consecutive y-coordinates
for j in range(len(ys) - 1):
y1, y2 = ys[j], ys[j+1]
if (y1, y2) in last_seen_segment_x:
prev_x = last_seen_segment_x[(y1, y2)]
# We need the index of prev_x in sorted_unique_xs to compare with seg tree results
# Since we don't store the index in the map, we might need a way to look it up
# OR, we can store (prev_x, prev_x_index) in the map.
# Let's refine the map: Key=(y1, y2), Value=(x_val, x_index)
# However, looking at the logic:
# We just need to know if there's any point in y-range [y1, y2]
# that appeared strictly after prev_x_index.
# Let's re-fetch the stored data properly.
pass
# Re-iterate to process logic correctly
pass
# Reset and implement the loop cleanly
last_seen_segment = {} # (y1, y2) -> (x_val, x_index)
for i, x in enumerate(sorted_unique_xs):
ys = points_by_x[x]
ys.sort()
# 1. Query and Check candidates
for j in range(len(ys) - 1):
y1, y2 = ys[j], ys[j+1]
rank1, rank2 = y_map[y1], y_map[y2]
if (y1, y2) in last_seen_segment:
prev_x, prev_x_idx = last_seen_segment[(y1, y2)]
# Check if any point exists in y-range [y1, y2] strictly after prev_x_idx
# The segment tree stores the max x-index seen so far for a y-rank.
# If max_idx > prev_x_idx, it means there is an obstruction.
max_idx_in_range = query(1, 0, m - 1, rank1, rank2)
if max_idx_in_range <= prev_x_idx:
area = (x - prev_x) * (y2 - y1)
if area > max_area:
max_area = area
# Even if invalid, we update the last seen for this segment to current
# because the old one can't form a valid rectangle with any future line
# if the current line blocked it or if it was valid (greedy approach for segments)
# Actually, for the specific pair (y1, y2), the current vertical line
# becomes the new potential left edge for future rectangles.
# Update the map for this segment to be the current x
last_seen_segment[(y1, y2)] = (x, i)
# 2. Update Segment Tree with current points
# We must do this AFTER checking segments to avoid self-interference
for y in ys:
update(1, 0, m - 1, y_map[y], i)
return max_area
# @lc code=end
// Accepted solution for LeetCode #3382: Maximum Area Rectangle With Point Constraints II
// Rust example auto-generated from go reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (go):
// // Accepted solution for LeetCode #3382: Maximum Area Rectangle With Point Constraints II
// package main
//
// import (
// "cmp"
// "slices"
// "sort"
// )
//
// // https://space.bilibili.com/206214
// type fenwick []int
//
// func (f fenwick) add(i int) {
// for ; i < len(f); i += i & -i {
// f[i]++
// }
// }
//
// func (f fenwick) pre(i int) (res int) {
// for ; i > 0; i &= i - 1 {
// res += f[i]
// }
// return
// }
//
// func (f fenwick) query(l, r int) int {
// return f.pre(r) - f.pre(l-1)
// }
//
// func maxRectangleArea(xCoord, ys []int) int64 {
// type pair struct{ x, y int }
// points := make([]pair, len(xCoord))
// for i := range xCoord {
// points[i] = pair{xCoord[i], ys[i]}
// }
// slices.SortFunc(points, func(a, b pair) int { return cmp.Or(a.x-b.x, a.y-b.y) })
//
// // 离散化用
// slices.Sort(ys)
// ys = slices.Compact(ys)
//
// ans := -1
// tree := make(fenwick, len(ys)+1)
// tree.add(sort.SearchInts(ys, points[0].y) + 1) // 离散化
// type tuple struct{ x, y, c int }
// pre := make([]tuple, len(ys))
// for i := 1; i < len(points); i++ {
// x1, y1 := points[i-1].x, points[i-1].y
// x2, y2 := points[i].x, points[i].y
// y := sort.SearchInts(ys, y2) // 离散化
// tree.add(y + 1)
// if x1 != x2 { // 两点不在同一列
// continue
// }
// cur := tree.query(sort.SearchInts(ys, y1)+1, y+1)
// p := pre[y]
// if p.c > 0 && p.c+2 == cur && p.y == y1 {
// ans = max(ans, (x2-p.x)*(y2-y1))
// }
// pre[y] = tuple{x1, y1, cur}
// }
// return int64(ans)
// }
// Accepted solution for LeetCode #3382: Maximum Area Rectangle With Point Constraints II
// Auto-generated TypeScript example from go.
function exampleSolution(): void {
}
// Reference (go):
// // Accepted solution for LeetCode #3382: Maximum Area Rectangle With Point Constraints II
// package main
//
// import (
// "cmp"
// "slices"
// "sort"
// )
//
// // https://space.bilibili.com/206214
// type fenwick []int
//
// func (f fenwick) add(i int) {
// for ; i < len(f); i += i & -i {
// f[i]++
// }
// }
//
// func (f fenwick) pre(i int) (res int) {
// for ; i > 0; i &= i - 1 {
// res += f[i]
// }
// return
// }
//
// func (f fenwick) query(l, r int) int {
// return f.pre(r) - f.pre(l-1)
// }
//
// func maxRectangleArea(xCoord, ys []int) int64 {
// type pair struct{ x, y int }
// points := make([]pair, len(xCoord))
// for i := range xCoord {
// points[i] = pair{xCoord[i], ys[i]}
// }
// slices.SortFunc(points, func(a, b pair) int { return cmp.Or(a.x-b.x, a.y-b.y) })
//
// // 离散化用
// slices.Sort(ys)
// ys = slices.Compact(ys)
//
// ans := -1
// tree := make(fenwick, len(ys)+1)
// tree.add(sort.SearchInts(ys, points[0].y) + 1) // 离散化
// type tuple struct{ x, y, c int }
// pre := make([]tuple, len(ys))
// for i := 1; i < len(points); i++ {
// x1, y1 := points[i-1].x, points[i-1].y
// x2, y2 := points[i].x, points[i].y
// y := sort.SearchInts(ys, y2) // 离散化
// tree.add(y + 1)
// if x1 != x2 { // 两点不在同一列
// continue
// }
// cur := tree.query(sort.SearchInts(ys, y1)+1, y+1)
// p := pre[y]
// if p.c > 0 && p.c+2 == cur && p.y == y1 {
// ans = max(ans, (x2-p.x)*(y2-y1))
// }
// pre[y] = tuple{x1, y1, cur}
// }
// return int64(ans)
// }
Use this to step through a reusable interview workflow for this problem.
For each of q queries, scan the entire range to compute the aggregate (sum, min, max). Each range scan takes up to O(n) for a full-array query. With q queries: O(n × q) total. Point updates are O(1) but queries dominate.
Building the tree is O(n). Each query or update traverses O(log n) nodes (tree height). For q queries: O(n + q log n) total. Space is O(4n) ≈ O(n) for the tree array. Lazy propagation adds O(1) per node for deferred updates.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.