Maximum Area Rectangle With Point Constraints II
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 i^th 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.
Example 1
Input
xCoord = [1,1,3,3], yCoord = [1,3,1,3]Output
4We can make a rectangle with these 4 points as corners and there is no other point that lies inside or on the border, so the maximum possible area is 4.
Example 2
Input
xCoord = [1,1,3,3,2], yCoord = [1,3,1,3,2]Output
-1The only possible rectangle uses points [1,1], [1,3], [3,1], and [3,3], but [2,2] lies inside it, so the answer is -1.
Constraints
- 1 <= xCoord.length == yCoord.length <= 2 * 10^5
- 0 <= xCoord[i], yCoord[i] <= 8 * 10^7
- All the given points are unique.