Maximum Area Rectangle With Point Constraints II

Hard

#3005Time: 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.1 company

Patterns

Math Geometry

Algorithms

Sorting

Data structures

Array Binary Indexed Tree Segment Tree

Companies

UKG

Prompt

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 i^th 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:

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 * 10⁵
0 <= xCoord[i], yCoord[i] <= 8 * 10⁷
All the given points are unique.

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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.
1. 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).
1. 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.
1. Perform a horizontal sweep by iterating through a sorted list of unique y-coordinates.
1. For each y, get its sorted list of x-coordinates xCoords from yMap.
1. Iterate through adjacent pairs (x1, x2) in xCoords. This pair forms an empty horizontal segment.
1. 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.
1. 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).
1. If all adjacency conditions hold, calculate the area and update maxArea.
1. Update lastYSeen with the current (x1, x2) pair and its y-coordinate y.

Walkthrough

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}

Complexity

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.

Trade-offs

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.

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.

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.
1. 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.
1. Initialize maxArea = -1.
1. Iterate through each point (x1, y1) in the input, treating it as a potential bottom-left corner.
1. 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.
1. 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.
1. Now we have three corners of a potential empty rectangle: (x1, y1), (x1, y2), (x2, y1). The fourth corner must be (x2, y2).
1. Check if the point (x2, y2) exists in the HashSet.
1. 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.
1. If all four adjacency conditions hold, the rectangle is guaranteed to be empty. Calculate its area and update maxArea.

Walkthrough

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.

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        Set<Long> pointSet = new HashSet<>();9 10        for (int i = 0; i < n; i++) {11            xMap.computeIfAbsent(xCoord[i], k -> new ArrayList<>()).add(yCoord[i]);12            yMap.computeIfAbsent(yCoord[i], k -> new ArrayList<>()).add(xCoord[i]);13            pointSet.add(pack(xCoord[i], yCoord[i]));14        }15 16        for (List<Integer> list : xMap.values()) Collections.sort(list);17        for (List<Integer> list : yMap.values()) Collections.sort(list);18 19        long maxArea = -1;20 21        for (int i = 0; i < n; i++) {22            int x1 = xCoord[i];23            int y1 = yCoord[i];24 25            List<Integer> yList = xMap.get(x1);26            List<Integer> xList = yMap.get(y1);27 28            int y1_idx = Collections.binarySearch(yList, y1);29            int x1_idx = Collections.binarySearch(xList, x1);30 31            // Consider points "up" and "right" from (x1, y1)32            if (y1_idx + 1 < yList.size() && x1_idx + 1 < xList.size()) {33                int y2 = yList.get(y1_idx + 1);34                int x2 = xList.get(x1_idx + 1);35 36                // Check if the 4th corner (x2, y2) exists37                if (pointSet.contains(pack(x2, y2))) {38                    // Verify the other two adjacency conditions39                    List<Integer> yListForX2 = xMap.get(x2);40                    int y1_idx_in_x2 = Collections.binarySearch(yListForX2, y1);41                    42                    List<Integer> xListForY2 = yMap.get(y2);43                    int x1_idx_in_y2 = Collections.binarySearch(xListForY2, x1);44 45                    if (y1_idx_in_x2 >= 0 && y1_idx_in_x2 + 1 < yListForX2.size() && yListForX2.get(y1_idx_in_x2 + 1) == y2 &&46                        x1_idx_in_y2 >= 0 && x1_idx_in_y2 + 1 < xListForY2.size() && xListForY2.get(x1_idx_in_y2 + 1) == x2) {47                        48                        long area = (long)(x2 - x1) * (y2 - y1);49                        if (maxArea == -1 || area > maxArea) {50                            maxArea = area;51                        }52                    }53                }54            }55        }56 57        return maxArea;58    }59 60    private long pack(long x, long y) {61        return (x << 32) | y;62    }63}

Complexity

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

Trade-offs

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

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.

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.
1. Initialize maxArea = -1.
1. Iterate through each point p1 from i = 0 to n-1.
1. Iterate through each other point p2 from j = i + 1 to n-1.
1. 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.
1. The other two corners would be p3 = (x1, y2) and p4 = (x2, y1). Check if points p3 and p4 exist in the HashSet.
1. If they exist, we have found a rectangle. Assume it's empty (isEmpty = true).
1. To verify emptiness, iterate through all n points p_check = (px, py).
1. 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.
1. If isEmpty remains true, calculate the area abs((long)(x2 - x1) * (y2 - y1)) and update maxArea.
1. After checking all pairs, return maxArea.

Walkthrough

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.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public long maxAreaRectangle(int[] xCoord, int[] yCoord) {6        int n = xCoord.length;7        long[][] points = new long[n][2];8        Set<Long> pointSet = new HashSet<>();9        for (int i = 0; i < n; i++) {10            points[i][0] = xCoord[i];11            points[i][1] = yCoord[i];12            pointSet.add(pack(xCoord[i], yCoord[i]));13        }14 15        long maxArea = -1;16 17        for (int i = 0; i < n; i++) {18            for (int j = i + 1; j < n; j++) {19                long x1 = points[i][0];20                long y1 = points[i][1];21                long x2 = points[j][0];22                long y2 = points[j][1];23 24                if (x1 == x2 || y1 == y2) {25                    continue;26                }27 28                if (pointSet.contains(pack(x1, y2)) && pointSet.contains(pack(x2, y1))) {29                    // Found a rectangle, now check if it's empty30                    boolean isEmpty = true;31                    for (int k = 0; k < n; k++) {32                        long px = points[k][0];33                        long py = points[k][1];34 35                        // Check if the point is one of the 4 corners36                        if ((px == x1 && py == y1) || (px == x1 && py == y2) || 37                            (px == x2 && py == y1) || (px == x2 && py == y2)) {38                            continue;39                        }40 41                        // Check if the point is inside or on the boundary42                        if (px >= Math.min(x1, x2) && px <= Math.max(x1, x2) &&43                            py >= Math.min(y1, y2) && py <= Math.max(y1, y2)) {44                            isEmpty = false;45                            break;46                        }47                    }48 49                    if (isEmpty) {50                        long area = Math.abs((x2 - x1) * (y2 - y1));51                        if (maxArea == -1 || area > maxArea) {52                            maxArea = area;53                        }54                    }55                }56            }57        }58 59        return maxArea;60    }61 62    private long pack(long x, long y) {63        return (x << 32) | y;64    }65}

Complexity

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.

Trade-offs

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.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem