Watch the video solution for Maximum Area Rectangle With Point Constraints II, a hard level problem involving Array, Math, Binary Indexed Tree. This walkthrough by Programming Live with Larry has 612 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 Overview: You are given a set of 2D points. The goal is to form an axis-aligned rectangle using four of those points as corners while satisfying additional constraints about points that lie between them. Among all valid rectangles, return the maximum possible area.
Approach 1: Brute Force Corner Enumeration (O(n^2) to O(n^3) time, O(n) space)
Start by treating every pair of points as potential diagonal corners of a rectangle. For each pair (x1, y1) and (x2, y2), compute the other two required corners (x1, y2) and (x2, y1) and check if they exist in a hash set. After confirming the four corners exist, scan the remaining points to ensure the rectangle satisfies the constraint conditions. This approach is easy to implement but expensive because each candidate rectangle may require scanning many points. Time complexity grows quickly as the number of points increases.
Approach 2: Sweep Line with Sorting + Binary Indexed Tree (O(n log n) time, O(n) space)
The optimized approach treats the plane as vertical sweep events. First sort all points by their x-coordinate using sorting. Compress the y-coordinates so they can be indexed efficiently. As the sweep line moves from left to right, process columns of points that share the same x value.
For every pair of y-coordinates in the current column, treat them as the potential vertical edges of a rectangle. Track the last x position where this same pair of y values appeared. If the pair appeared before, a rectangle is formed between the previous column and the current column. To verify the rectangle satisfies the point constraints, query a Binary Indexed Tree (Fenwick Tree) or Segment Tree to ensure no conflicting points lie inside the vertical range between the two columns.
The key insight is that the sweep converts a 2D geometry problem into repeated range queries on compressed y indices. Fenwick tree prefix sums allow fast checks of how many points lie in a vertical interval. Each update and query runs in O(log n), producing an overall O(n log n) algorithm that scales to large inputs.
Recommended for interviews: The sweep line with Binary Indexed Tree solution is what interviewers expect for a Hard geometry problem. Brute force shows you understand rectangle construction, but the optimized approach demonstrates knowledge of array indexing tricks, coordinate compression, and efficient range queries.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Corner Enumeration | O(n^2) to O(n^3) | O(n) | Useful for understanding rectangle formation logic or when the number of points is very small. |
| Sweep Line + Binary Indexed Tree | O(n log n) | O(n) | Best for large inputs. Efficient range queries ensure rectangle constraints are checked quickly. |