#3382
Maximum Area Rectangle With Point Constraints II
hard · 23.8% accepted · 48 likes · top 3%
array · math · binary indexed tree · segment tree · geometry · sorting
Description
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.
Solution