Maximum Area Rectangle With Point Constraints II

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.

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

import java.util.*;

class Solution {
    public long maxAreaRectangle(int[] xCoord, int[] yCoord) {
        int n = xCoord.length;
        Map<Integer, List<Integer>> xMap = new HashMap<>();
        Map<Integer, List<Integer>> 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<Integer> list : xMap.values()) {
            Collections.sort(list);
        }
        for (List<Integer> list : yMap.values()) {
            Collections.sort(list);
        }

        List<Integer> sortedY = new ArrayList<>(yMap.keySet());
        Collections.sort(sortedY);

        long maxArea = -1;
        Map<Long, Integer> lastYSeen = new HashMap<>();

        for (int y : sortedY) {
            List<Integer> 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<Integer, List<Integer>> xMap, int x, int y1, int y2) {
        List<Integer> 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;
    }
}