# Maximum Area Rectangle With Point Constraints II **Difficulty:** HARD [External](https://leetcode.com/problems/maximum-area-rectangle-with-point-constraints-ii) Canonical: https://scaleengineer.com/dsa/problems/maximum-area-rectangle-with-point-constraints-ii **Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry) **Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting) **Data structures:** Array, Binary Indexed Tree, Segment Tree **Companies:** [UKG](https://scaleengineer.com/companies/ukg) --- ## Problem 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. **Example 1:** **Input:** xCoord = \[1,1,3,3\], yCoord = \[1,3,1,3\] **Output:** 4 **Explanation:** **![Example 1 diagram](https://assets.glich.co/dsa/maximum-area-rectangle-with-point-constraints-ii/image0.png)** 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:** **![Example 2 diagram](https://assets.glich.co/dsa/maximum-area-rectangle-with-point-constraints-ii/image1.png)** 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:** **![Example 3 diagram](https://assets.glich.co/dsa/maximum-area-rectangle-with-point-constraints-ii/image2.png)** 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 * 105` * `0 <= xCoord[i], yCoord[i] <= 8 * 107` * All the given points are **unique**. # Approaches ## Brute-Force with Point Set This approach iterates through all possible pairs of points, considering them as potential diagonals of a rectangle. For each potential rectangle, it first verifies that all four corner points exist in the input set. Then, it checks the emptiness condition by performing a linear scan through all other points to ensure none lie inside or on the rectangle's boundary. **Time:** O(N^3), where N is the number of points. We iterate through `O(N^2)` pairs of points. For each potential rectangle found, we perform an emptiness check which takes `O(N)` time. · **Space:** O(N), where N is the number of points. This is required to store the points in a `HashSet` for efficient lookups. **Pros:** Relatively simple to understand and implement the logic.; Correctly solves the problem for small input sizes. **Cons:** The `O(N^3)` time complexity is highly inefficient and will result in a 'Time Limit Exceeded' error for the given constraints. ### Explanation First, we store all points in a `HashSet` to allow for quick, `O(1)` average time lookups. A point `(x, y)` can be uniquely represented as a `long` by packing its coordinates, for instance, `(long)x << 32 | y`. Then, we iterate through every unique pair of points `p1(x1, y1)` and `p2(x2, y2)`. If `x1 == x2` or `y1 == y2`, these points lie on the same horizontal or vertical line and cannot form a non-degenerate rectangle's diagonal, so we skip them. Otherwise, we form the other two potential corners `p3(x1, y2)` and `p4(x2, y1)`. We check if `p3` and `p4` exist in our `HashSet`. If they do, we have found the four corners of an axis-aligned rectangle. The crucial and most expensive step is to verify that this rectangle is "empty". We do this by iterating through all `n` points in the input. For each point, we check if it lies inside or on the boundary of our rectangle, making sure it's not one of the four corner points. If no such other points are found, the rectangle is valid. We calculate its area and update our maximum area found so far. This process is repeated for all `O(N^2)` pairs of points. ```java import java.util.HashSet; import java.util.Set; class Solution { public long maxAreaRectangle(int[] xCoord, int[] yCoord) { int n = xCoord.length; long[][] points = new long[n][2]; Set pointSet = new HashSet<>(); for (int i = 0; i < n; i++) { points[i][0] = xCoord[i]; points[i][1] = yCoord[i]; pointSet.add(pack(xCoord[i], yCoord[i])); } long maxArea = -1; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { long x1 = points[i][0]; long y1 = points[i][1]; long x2 = points[j][0]; long y2 = points[j][1]; if (x1 == x2 || y1 == y2) { continue; } if (pointSet.contains(pack(x1, y2)) && pointSet.contains(pack(x2, y1))) { // Found a rectangle, now check if it's empty boolean isEmpty = true; for (int k = 0; k < n; k++) { long px = points[k][0]; long py = points[k][1]; // Check if the point is one of the 4 corners if ((px == x1 && py == y1) || (px == x1 && py == y2) || (px == x2 && py == y1) || (px == x2 && py == y2)) { continue; } // Check if the point is inside or on the boundary if (px >= Math.min(x1, x2) && px <= Math.max(x1, x2) && py >= Math.min(y1, y2) && py <= Math.max(y1, y2)) { isEmpty = false; break; } } if (isEmpty) { long area = Math.abs((x2 - x1) * (y2 - y1)); if (maxArea == -1 || area > maxArea) { maxArea = area; } } } } } return maxArea; } private long pack(long x, long y) { return (x << 32) | y; } } ``` ### Algorithm - 1. Store all `n` points in a `HashSet` for `O(1)` average time lookups. A point can be represented as a `long` by packing its x and y coordinates. - 2. Initialize `maxArea = -1`. - 3. Iterate through each point `p1` from `i = 0` to `n-1`. - 4. Iterate through each other point `p2` from `j = i + 1` to `n-1`. - 5. Let `p1 = (x1, y1)` and `p2 = (x2, y2)`. If `x1 == x2` or `y1 == y2`, these points cannot form a non-degenerate rectangle's diagonal, so we skip them. - 6. The other two corners would be `p3 = (x1, y2)` and `p4 = (x2, y1)`. Check if points `p3` and `p4` exist in the `HashSet`. - 7. If they exist, we have found a rectangle. Assume it's empty (`isEmpty = true`). - 8. To verify emptiness, iterate through all `n` points `p_check = (px, py)`. - 9. If `p_check` is not one of the four corners and it lies within the rectangle's bounds (`min(x1,x2) <= px <= max(x1,x2)` and `min(y1,y2) <= py <= max(y1,y2)`), set `isEmpty = false` and break the check. - 10. If `isEmpty` remains true, calculate the area `abs((long)(x2 - x1) * (y2 - y1))` and update `maxArea`. - 11. After checking all pairs, return `maxArea`. ## Sweep-Line Algorithm This approach improves upon the brute-force method by using a sweep-line technique. It processes the points sorted by one coordinate (e.g., y-coordinate) and uses a hash map to keep track of potential rectangle edges seen so far. This avoids the `O(N^3)` complexity by intelligently constructing and verifying only the rectangles that have a chance of being empty. **Time:** O(N log N), where N is the number of points. The preprocessing step of creating and sorting the lists in the maps takes `O(N log N)`. The sweep-line itself involves iterating through `O(N)` adjacent pairs in total, with each check involving binary searches (`O(log N)`), leading to a total time complexity of `O(N log N)`. · **Space:** O(N), where N is the number of points. This space is used for the `xMap`, `yMap`, and the `lastYSeen` map, all of which can store up to `O(N)` elements or pairs in total. **Pros:** Efficient `O(N log N)` time complexity, which is suitable for the given constraints.; Systematically finds all valid empty rectangles. **Cons:** The implementation is more complex than the brute-force approach.; Requires careful management of multiple data structures and understanding of the geometric properties. ### Explanation The core idea is based on the insight that an empty rectangle must be bounded by adjacent points. For a rectangle with corners `(x1, y1), (x2, y1), (x1, y2), (x2, y2)` to be empty, its horizontal and vertical edges must not contain any other points. We can implement this with a horizontal sweep-line algorithm. We first pre-process all points into two maps: one mapping x-coordinates to their sorted y-coordinates (`xMap`), and another mapping y-coordinates to their sorted x-coordinates (`yMap`). We then sweep a line from bottom to top by iterating through the unique y-coordinates in sorted order. At each `y` level, we look at the points on that line. We consider every adjacent pair of points `(x1, y)` and `(x2, y)`. This forms an empty horizontal segment. We use a hash map, `lastYSeen`, to remember the `y`-coordinate where we last saw the horizontal segment defined by `(x1, x2)`. If we find the pair `(x1, x2)` in our map, it means we have found a previous empty horizontal segment at `prevY` with the same x-coordinates. This gives us a rectangle with empty top and bottom edges. The final step is to verify that the vertical edges are also empty. We do this by using our `xMap` to check if `y` is the immediate successor of `prevY` in the sorted y-lists for both `x1` and `x2`. If this holds, the rectangle is empty, and we update our maximum area. ```java import java.util.*; class Solution { public long maxAreaRectangle(int[] xCoord, int[] yCoord) { int n = xCoord.length; Map> xMap = new HashMap<>(); Map> yMap = new HashMap<>(); for (int i = 0; i < n; i++) { xMap.computeIfAbsent(xCoord[i], k -> new ArrayList<>()).add(yCoord[i]); yMap.computeIfAbsent(yCoord[i], k -> new ArrayList<>()).add(xCoord[i]); } for (List list : xMap.values()) { Collections.sort(list); } for (List list : yMap.values()) { Collections.sort(list); } List sortedY = new ArrayList<>(yMap.keySet()); Collections.sort(sortedY); long maxArea = -1; Map lastYSeen = new HashMap<>(); for (int y : sortedY) { List xCoords = yMap.get(y); for (int i = 0; i < xCoords.size() - 1; i++) { int x1 = xCoords.get(i); int x2 = xCoords.get(i + 1); long pairKey = pack(x1, x2); if (lastYSeen.containsKey(pairKey)) { int prevY = lastYSeen.get(pairKey); // Check vertical adjacency if (isVerticallyAdjacent(xMap, x1, prevY, y) && isVerticallyAdjacent(xMap, x2, prevY, y)) { long area = (long)(x2 - x1) * (y - prevY); if (maxArea == -1 || area > maxArea) { maxArea = area; } } } lastYSeen.put(pairKey, y); } } return maxArea; } private boolean isVerticallyAdjacent(Map> xMap, int x, int y1, int y2) { List yList = xMap.get(x); int idx = Collections.binarySearch(yList, y1); return idx >= 0 && idx + 1 < yList.size() && yList.get(idx + 1) == y2; } private long pack(int x1, int x2) { return ((long)x1 << 32) | x2; } } ``` ### Algorithm - 1. Establish the necessary and sufficient conditions for an empty rectangle: its four edges must be empty of other points. This implies that its corners are formed by points that are mutually adjacent in the point-defined grid. - 2. Pre-process the points into two maps: `xMap` (mapping each x-coordinate to a sorted list of its y-coordinates) and `yMap` (mapping each y-coordinate to a sorted list of its x-coordinates). - 3. Initialize `maxArea = -1` and a hash map `lastYSeen`. This map will store, for a pair of x-coordinates `(x1, x2)`, the y-coordinate where they last appeared as an adjacent horizontal segment. - 4. Perform a horizontal sweep by iterating through a sorted list of unique y-coordinates. - 5. For each `y`, get its sorted list of x-coordinates `xCoords` from `yMap`. - 6. Iterate through adjacent pairs `(x1, x2)` in `xCoords`. This pair forms an empty horizontal segment. - 7. Check if the pair `(x1, x2)` exists as a key in `lastYSeen`. If it does, with a value `prevY`, we have a candidate rectangle with empty top and bottom edges. - 8. Verify that the vertical edges are also empty. This is done by checking if `y` is the immediate successor of `prevY` in the sorted y-lists for both `x1` and `x2` (from `xMap`). - 9. If all adjacency conditions hold, calculate the area and update `maxArea`. - 10. Update `lastYSeen` with the current `(x1, x2)` pair and its y-coordinate `y`. ## Grid Adjacency Check This is arguably the most elegant and efficient approach. It is based on a crucial insight into the geometric structure of empty rectangles. It establishes that for a rectangle to be empty, its corners must be formed by points that are mutually adjacent in the grid defined by the input points themselves. **Time:** O(N log N), where N is the number of points. Preprocessing takes `O(N log N)`. The main loop iterates N times, and inside the loop, we perform a constant number of binary searches (`O(log N)`) on lists of size at most N. This results in a total time of `O(N log N)`. · **Space:** O(N), where N is the number of points. Space is needed for the `xMap`, `yMap`, and the `pointSet`. **Pros:** Highly efficient with `O(N log N)` time complexity.; Conceptually clean and direct once the geometric property is understood.; Guaranteed to be correct and avoids complex state management seen in some sweep-line variants. **Cons:** The logic relies on a non-trivial geometric insight which might not be immediately obvious.; Requires significant preprocessing to build multiple data structures (`xMap`, `yMap`, `pointSet`). ### Explanation The fundamental property of an empty rectangle defined by `(x1, y1), (x2, y1), (x1, y2), (x2, y2)` is that there are no other input points on its boundary or in its interior. This implies a set of strong adjacency conditions that are both necessary and sufficient: - `y1` and `y2` must be adjacent y-coordinates among all points with x-coordinate `x1`. - `y1` and `y2` must also be adjacent for x-coordinate `x2`. - Similarly, `x1` and `x2` must be adjacent x-coordinates for y-coordinate `y1`. - `x1` and `x2` must also be adjacent for y-coordinate `y2`. This approach leverages this property by iterating through each point and treating it as a potential bottom-left corner. For each point `(x1, y1)`, it finds its "up" neighbor `(x1, y2)` and "right" neighbor `(x2, y1)` using pre-processed maps. These maps store sorted lists of coordinates, allowing for efficient neighbor lookups using binary search. These three points define the potential fourth corner `(x2, y2)`. If this fourth corner exists, the algorithm then simply verifies the remaining two adjacency conditions to confirm the rectangle is empty. Because we check every point as a potential corner, we are guaranteed to find the maximum area empty rectangle. ```java import java.util.*; class Solution { public long maxAreaRectangle(int[] xCoord, int[] yCoord) { int n = xCoord.length; Map> xMap = new HashMap<>(); Map> yMap = new HashMap<>(); Set pointSet = new HashSet<>(); for (int i = 0; i < n; i++) { xMap.computeIfAbsent(xCoord[i], k -> new ArrayList<>()).add(yCoord[i]); yMap.computeIfAbsent(yCoord[i], k -> new ArrayList<>()).add(xCoord[i]); pointSet.add(pack(xCoord[i], yCoord[i])); } for (List list : xMap.values()) Collections.sort(list); for (List list : yMap.values()) Collections.sort(list); long maxArea = -1; for (int i = 0; i < n; i++) { int x1 = xCoord[i]; int y1 = yCoord[i]; List yList = xMap.get(x1); List xList = yMap.get(y1); int y1_idx = Collections.binarySearch(yList, y1); int x1_idx = Collections.binarySearch(xList, x1); // Consider points "up" and "right" from (x1, y1) if (y1_idx + 1 < yList.size() && x1_idx + 1 < xList.size()) { int y2 = yList.get(y1_idx + 1); int x2 = xList.get(x1_idx + 1); // Check if the 4th corner (x2, y2) exists if (pointSet.contains(pack(x2, y2))) { // Verify the other two adjacency conditions List yListForX2 = xMap.get(x2); int y1_idx_in_x2 = Collections.binarySearch(yListForX2, y1); List xListForY2 = yMap.get(y2); int x1_idx_in_y2 = Collections.binarySearch(xListForY2, x1); if (y1_idx_in_x2 >= 0 && y1_idx_in_x2 + 1 < yListForX2.size() && yListForX2.get(y1_idx_in_x2 + 1) == y2 && x1_idx_in_y2 >= 0 && x1_idx_in_y2 + 1 < xListForY2.size() && xListForY2.get(x1_idx_in_y2 + 1) == x2) { long area = (long)(x2 - x1) * (y2 - y1); if (maxArea == -1 || area > maxArea) { maxArea = area; } } } } } return maxArea; } private long pack(long x, long y) { return (x << 32) | y; } } ``` ### Algorithm - 1. Discover the key property: A rectangle is empty if and only if its four corners `(x1, y1), (x1, y2), (x2, y1), (x2, y2)` are all input points, and they are mutually adjacent in the grid formed by the points. - 2. Pre-process the points into `xMap` (x -> sorted list of y's), `yMap` (y -> sorted list of x's), and a `HashSet` of all points for `O(1)` existence checks. - 3. Initialize `maxArea = -1`. - 4. Iterate through each point `(x1, y1)` in the input, treating it as a potential bottom-left corner. - 5. Using `xMap`, find the y-coordinate `y2` that is immediately after `y1` for the x-coordinate `x1`. This gives the 'up' neighbor. If none exists, continue. - 6. Using `yMap`, find the x-coordinate `x2` that is immediately after `x1` for the y-coordinate `y1`. This gives the 'right' neighbor. If none exists, continue. - 7. Now we have three corners of a potential empty rectangle: `(x1, y1), (x1, y2), (x2, y1)`. The fourth corner must be `(x2, y2)`. - 8. Check if the point `(x2, y2)` exists in the `HashSet`. - 9. If it exists, verify the remaining two adjacency conditions: Is `y2` adjacent to `y1` for `x2`? Is `x2` adjacent to `x1` for `y2`? These checks are done via binary search in the pre-processed maps. - 10. If all four adjacency conditions hold, the rectangle is guaranteed to be empty. Calculate its area and update `maxArea`.