Maximum Area Rectangle With Point Constraints II

Problem 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.

Key Insights

• A rectangle can only be formed if we have two unique x-coordinates and two unique y-coordinates.
• We need to ensure that no other points lie within or on the border of the rectangle formed by the selected corners.
• A brute-force approach would be inefficient; an optimal solution requires sorting and efficient range checking.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the coordinates. Space Complexity: O(n) - for storing the coordinates in sets for quick lookups.

Solution

To solve this problem, we can use the following approach:

1. Store the points in a set for O(1) lookup.
2. Extract unique x and y coordinates from the given points.
3. Sort the unique coordinates.
4. Iterate through pairs of unique x-coordinates and pairs of unique y-coordinates to form potential rectangles.
5. For each rectangle, check if any other point lies inside or on the border using the set.
6. Calculate the area and keep track of the maximum area found.

Code Solutions