Maximum Area Rectangle With Point Constraints II

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

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.

1import java.util.*;2 3class Solution {4    public long maxAreaRectangle(int[] xCoord, int[] yCoord) {5        int n = xCoord.length;6        Map<Integer, List<Integer>> xMap = new HashMap<>();7        Map<Integer, List<Integer>> yMap = new HashMap<>();8 9        for (int i = 0; i < n; i++) {10            xMap.computeIfAbsent(xCoord[i], k -> new ArrayList<>()).add(yCoord[i]);11            yMap.computeIfAbsent(yCoord[i], k -> new ArrayList<>()).add(xCoord[i]);12        }13 14        for (List<Integer> list : xMap.values()) {15            Collections.sort(list);16        }17        for (List<Integer> list : yMap.values()) {18            Collections.sort(list);19        }20 21        List<Integer> sortedY = new ArrayList<>(yMap.keySet());22        Collections.sort(sortedY);23 24        long maxArea = -1;25        Map<Long, Integer> lastYSeen = new HashMap<>();26 27        for (int y : sortedY) {28            List<Integer> xCoords = yMap.get(y);29            for (int i = 0; i < xCoords.size() - 1; i++) {30                int x1 = xCoords.get(i);31                int x2 = xCoords.get(i + 1);32                long pairKey = pack(x1, x2);33 34                if (lastYSeen.containsKey(pairKey)) {35                    int prevY = lastYSeen.get(pairKey);36                    37                    // Check vertical adjacency38                    if (isVerticallyAdjacent(xMap, x1, prevY, y) && isVerticallyAdjacent(xMap, x2, prevY, y)) {39                        long area = (long)(x2 - x1) * (y - prevY);40                        if (maxArea == -1 || area > maxArea) {41                            maxArea = area;42                        }43                    }44                }45                lastYSeen.put(pairKey, y);46            }47        }48 49        return maxArea;50    }51 52    private boolean isVerticallyAdjacent(Map<Integer, List<Integer>> xMap, int x, int y1, int y2) {53        List<Integer> yList = xMap.get(x);54        int idx = Collections.binarySearch(yList, y1);55        return idx >= 0 && idx + 1 < yList.size() && yList.get(idx + 1) == y2;56    }57 58    private long pack(int x1, int x2) {59        return ((long)x1 << 32) | x2;60    }61}