3382. Maximum Area Rectangle With Point Constraints II
Hard
50 Points
Array
Math
Binary Indexed Tree
Segment Tree
Geometry
Sorting
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.
Examples
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 * 107All the given points are unique.
3382. Maximum Area Rectangle With Point Constraints II
Hard
50 Points
Array
Math
Binary Indexed Tree
Segment Tree
Geometry
Sorting
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.
Examples
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 * 107All the given points are unique.