Maximum Area Rectangle With Point Constraints I

Med

#3003Time: O(N^5), where N is the number of points. There are O(N^4) combinations of four points. For each combination, we check the emptiness condition by iterating through the other O(N) points.Space: O(1), as we only use a few variables to store coordinates and the max area, not dependent on the input size.1 company

Patterns

Math Geometry Enumeration

Algorithms

Sorting

Data structures

Array Binary Indexed Tree Segment Tree

Companies

UKG

Prompt

You are given an array points where points[i] = [x_i, y_i] represents the coordinates of a point on an infinite plane.

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: points = [[1,1],[1,3],[3,1],[3,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: points = [[1,1],[1,3],[3,1],[3,3],[2,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: points = [[1,1],[1,3],[3,1],[3,3],[1,2],[3,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 <= points.length <= 10
points[i].length == 2
0 <= x_i, y_i <= 100
All the given points are unique.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach exhaustively checks every possible combination of four points from the input array to see if they can form a valid, empty, axis-aligned rectangle. Given the small constraint on the number of points (N <= 10), this method is feasible despite its high time complexity.

Algorithm

Initialize a variable maxArea to -1 to store the maximum valid area found.
Use four nested loops to iterate through all unique combinations of four points from the input array points. Let the chosen points be p1, p2, p3, and p4.
For each quartet of points, verify if they can form an axis-aligned rectangle. This is true if the set of their x-coordinates and the set of their y-coordinates each contain exactly two unique values.
If they form a rectangle, determine its boundaries by finding the minimum and maximum x and y coordinates (x_min, x_max, y_min, y_max).
Check the emptiness condition: Iterate through all points in the original points array. If any point that is not one of the four corners lies within or on the boundary of the rectangle (i.e., its coordinates (px, py) satisfy x_min <= px <= x_max and y_min <= py <= y_max), the rectangle is considered not empty and is invalid.
If the rectangle is confirmed to be empty, calculate its area as (x_max - x_min) * (y_max - y_min).
Update maxArea by taking the maximum of the current maxArea and the newly calculated area.
After checking all possible combinations, return the final maxArea.

Walkthrough

The core idea is to use brute force. Since a rectangle requires four corners, we can generate all possible sets of four points from the input list. The number of combinations is given by N C 4, where N is the total number of points. For each combination, we perform two checks:

Rectangle Formation Check: We verify if the four points can form an axis-aligned rectangle. This is done by checking their coordinates. If there are exactly two distinct x-values and two distinct y-values among the four points, they form a rectangle.
Emptiness Check: If the points form a rectangle, we then check if it's 'empty'. An empty rectangle is one that does not contain any other input points on its boundary or in its interior. We iterate through all the points in the input array that are not part of the current quartet. If any of these points fall within the rectangle's bounding box, the rectangle is invalid.

If a rectangle passes both checks, we calculate its area and update our maximum area found so far. If no such rectangle is found after checking all combinations, the initial value of -1 is returned.

1class Solution {2    public int maxAreaRectangle(int[][] points) {3        int n = points.length;4        if (n < 4) {5            return -1;6        }7        long maxArea = -1;8 9        for (int i = 0; i < n; i++) {10            for (int j = i + 1; j < n; j++) {11                for (int k = j + 1; k < n; k++) {12                    for (int l = k + 1; l < n; l++) {13                        int[] p1 = points[i];14                        int[] p2 = points[j];15                        int[] p3 = points[k];16                        int[] p4 = points[l];17 18                        java.util.Set<Integer> xCoords = new java.util.HashSet<>();19                        java.util.Set<Integer> yCoords = new java.util.HashSet<>();20                        xCoords.add(p1[0]); xCoords.add(p2[0]); xCoords.add(p3[0]); xCoords.add(p4[0]);21                        yCoords.add(p1[1]); yCoords.add(p2[1]); yCoords.add(p3[1]); yCoords.add(p4[1]);22 23                        if (xCoords.size() == 2 && yCoords.size() == 2) {24                            int x_min = java.util.Collections.min(xCoords);25                            int x_max = java.util.Collections.max(xCoords);26                            int y_min = java.util.Collections.min(yCoords);27                            int y_max = java.util.Collections.max(yCoords);28 29                            boolean isEmpty = true;30                            for (int m = 0; m < n; m++) {31                                if (m == i || m == j || m == k || m == l) {32                                    continue;33                                }34                                int[] otherPoint = points[m];35                                if (otherPoint[0] >= x_min && otherPoint[0] <= x_max &&36                                    otherPoint[1] >= y_min && otherPoint[1] <= y_max) {37                                    isEmpty = false;38                                    break;39                                }40                            }41 42                            if (isEmpty) {43                                long area = (long)(x_max - x_min) * (y_max - y_min);44                                maxArea = Math.max(maxArea, area);45                            }46                        }47                    } 48                }49            }50        }51        return (int)maxArea;52    }53}

Complexity

Time

O(N^5), where N is the number of points. There are O(N^4) combinations of four points. For each combination, we check the emptiness condition by iterating through the other O(N) points.

Space

O(1), as we only use a few variables to store coordinates and the max area, not dependent on the input size.

Trade-offs

Pros

Simple to understand and implement.
Requires no extra space.

Cons

The time complexity is very high, making it impractical for larger datasets.

A more efficient method involves iterating through all pairs of points and treating them as potential diagonal corners of a rectangle. By using a hash set for quick lookups of the other two corners, we can find candidate rectangles much faster than the four-point combination approach.

Algorithm

First, store all input points in a HashSet to allow for constant-time average lookups. A common way to do this is to convert each point [x, y] into a string like "x,y" to use as the key.
Initialize a variable maxArea to -1.
Iterate through all unique pairs of points from the input array, let's say p1 = (x1, y1) and p2 = (x2, y2).
For each pair, check if they can form a diagonal of an axis-aligned rectangle. This is possible only if x1 != x2 and y1 != y2.
If they can form a diagonal, the other two corners of the rectangle would be p3 = (x1, y2) and p4 = (x2, y1). Check if both p3 and p4 exist in the HashSet.
If all four corners exist, we have found a candidate rectangle. Now, check if it's empty.
To check for emptiness, iterate through all N input points. If any point (that is not one of the four corners) lies inside or on the boundary of the rectangle, the rectangle is invalid.
If the rectangle is empty, calculate its area: abs(x1 - x2) * abs(y1 - y2).
Update maxArea with the current area if it's larger.
After checking all pairs, return the final maxArea.

Walkthrough

This optimized approach reduces the complexity of finding rectangles. Instead of picking four points, we pick two points, p1(x1, y1) and p2(x2, y2), and assume they are diagonally opposite corners. For this to be possible, their x and y coordinates must be different.

The other two corners required to complete the rectangle would be at (x1, y2) and (x2, y1). We can check for the existence of these two points very quickly if we pre-process all input points into a HashSet.

Once a four-corner rectangle is identified, we perform the same emptiness check as in the brute-force approach: we iterate through all input points to ensure no other point lies within the rectangle's boundaries. If the rectangle is empty, we calculate its area and update the maximum area found.

This method reduces the complexity of finding candidate rectangles from O(N^4) to O(N^2), leading to a significant overall performance improvement.

1class Solution {2    public int maxAreaRectangle(int[][] points) {3        int n = points.length;4        if (n < 4) {5            return -1;6        }7 8        java.util.Set<String> pointSet = new java.util.HashSet<>();9        for (int[] p : points) {10            pointSet.add(p[0] + "," + p[1]);11        }12 13        long maxArea = -1;14 15        for (int i = 0; i < n; i++) {16            for (int j = i + 1; j < n; j++) {17                int[] p1 = points[i];18                int[] p2 = points[j];19                int x1 = p1[0], y1 = p1[1];20                int x2 = p2[0], y2 = p2[1];21 22                if (x1 == x2 || y1 == y2) {23                    continue;24                }25 26                // Check if the other two corners exist27                if (pointSet.contains(x1 + "," + y2) && pointSet.contains(x2 + "," + y1)) {28                    int x_min = Math.min(x1, x2);29                    int x_max = Math.max(x1, x2);30                    int y_min = Math.min(y1, y2);31                    int y_max = Math.max(y1, y2);32 33                    boolean isEmpty = true;34                    for (int[] p_check : points) {35                        boolean isCorner = (p_check[0] == x1 && p_check[1] == y1) ||36                                           (p_check[0] == x2 && p_check[1] == y2) ||37                                           (p_check[0] == x1 && p_check[1] == y2) ||38                                           (p_check[0] == x2 && p_check[1] == y1);39                        if (isCorner) {40                            continue;41                        }42 43                        if (p_check[0] >= x_min && p_check[0] <= x_max &&44                            p_check[1] >= y_min && p_check[1] <= y_max) {45                            isEmpty = false;46                            break;47                        }48                    }49 50                    if (isEmpty) {51                        long area = (long)(x_max - x_min) * (y_max - y_min);52                        maxArea = Math.max(maxArea, area);53                    }54                }55            }56        }57        return (int)maxArea;58    }59}

Complexity

Time

O(N^3), where N is the number of points. We iterate through O(N^2) pairs of points. For each pair, we perform an O(1) lookup for the other corners and then an O(N) scan for the emptiness check.

Space

O(N) to store the N points in a `HashSet` for efficient lookups.

Trade-offs

Pros

Significantly faster than the brute-force approach.
Still conceptually straightforward.

Cons

Requires extra space to store the points in a hash set.

Solutions

Solution

1class Solution {2public3  int maxRectangleArea(int[][] points) {4    int ans = -1;5    for (int i = 0; i < points.length; ++i) {6      int x1 = points[i][0], y1 = points[i][1];7      for (int j = 0; j < i; ++j) {8        int x2 = points[j][0], y2 = points[j][1];9        int x3 = Math.min(x1, x2), y3 = Math.min(y1, y2);10        int x4 = Math.max(x1, x2), y4 = Math.max(y1, y2);11        if (check(points, x3, y3, x4, y4)) {12          ans = Math.max(ans, (x4 - x3) * (y4 - y3));13        }14      }15    }16    return ans;17  }18private19  boolean check(int[][] points, int x1, int y1, int x2, int y2) {20    int cnt = 0;21    for (var p : points) {22      int x = p[0];23      int y = p[1];24      if (x < x1 || x > x2 || y < y1 || y > y2) {25        continue;26      }27      if ((x == x1 || x == x2) && (y == y1 || y == y2)) {28        cnt++;29        continue;30      }31      return false;32    }33    return cnt == 4;34  }35}

1class Solution {2public:3  int maxRectangleArea(vector<vector<int>> &points) {4    auto check = [&](int x1, int y1, int x2, int y2) -> bool {5      int cnt = 0;6      for (const auto &point : points) {7        int x = point[0];8        int y = point[1];9        if (x < x1 || x > x2 || y < y1 || y > y2) {10          continue;11        }12        if ((x == x1 || x == x2) && (y == y1 || y == y2)) {13          cnt++;14          continue;15        }16        return false;17      }18      return cnt == 4;19    };20    int ans = -1;21    for (int i = 0; i < points.size(); i++) {22      int x1 = points[i][0], y1 = points[i][1];23      for (int j = 0; j < i; j++) {24        int x2 = points[j][0], y2 = points[j][1];25        int x3 = min(x1, x2), y3 = min(y1, y2);26        int x4 = max(x1, x2), y4 = max(y1, y2);27        if (check(x3, y3, x4, y4)) {28          ans = max(ans, (x4 - x3) * (y4 - y3));29        }30      }31    }32    return ans;33  }34};

1class Solution:2    def maxRectangleArea(self, points: List[List[int]]) -> int: def check(x1: int, y1: int, x2: int, y2: int) -> bool: cnt = 0 for x, y in points: if x < x1 or x > x2 or y < y1 or y > y2: continue if (x == x1 or x == x2) and (y == y1 or y == y2): cnt += 1 continue return False return cnt == 4 ans = - 1 for i, (x1, y1) in enumerate(points): for x2, y2 in points[: i]: x3, y3 = min(x1, x2), min(y1, y2) x4, y4 = max(x1, x2), max(y1, y2) if check(x3, y3, x4, y4): ans = max(ans, (x4 - x3) * (y4 - y3)) return ans

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

Solution

1class Solution {2public3  int maxRectangleArea(int[][] points) {4    int ans = -1;5    for (int i = 0; i < points.length; ++i) {6      int x1 = points[i][0], y1 = points[i][1];7      for (int j = 0; j < i; ++j) {8        int x2 = points[j][0], y2 = points[j][1];9        int x3 = Math.min(x1, x2), y3 = Math.min(y1, y2);10        int x4 = Math.max(x1, x2), y4 = Math.max(y1, y2);11        if (check(points, x3, y3, x4, y4)) {12          ans = Math.max(ans, (x4 - x3) * (y4 - y3));13        }14      }15    }16    return ans;17  }18private19  boolean check(int[][] points, int x1, int y1, int x2, int y2) {20    int cnt = 0;21    for (var p : points) {22      int x = p[0];23      int y = p[1];24      if (x < x1 || x > x2 || y < y1 || y > y2) {25        continue;26      }27      if ((x == x1 || x == x2) && (y == y1 || y == y2)) {28        cnt++;29        continue;30      }31      return false;32    }33    return cnt == 4;34  }35}

1class Solution {2public:3  int maxRectangleArea(vector<vector<int>> &points) {4    auto check = [&](int x1, int y1, int x2, int y2) -> bool {5      int cnt = 0;6      for (const auto &point : points) {7        int x = point[0];8        int y = point[1];9        if (x < x1 || x > x2 || y < y1 || y > y2) {10          continue;11        }12        if ((x == x1 || x == x2) && (y == y1 || y == y2)) {13          cnt++;14          continue;15        }16        return false;17      }18      return cnt == 4;19    };20    int ans = -1;21    for (int i = 0; i < points.size(); i++) {22      int x1 = points[i][0], y1 = points[i][1];23      for (int j = 0; j < i; j++) {24        int x2 = points[j][0], y2 = points[j][1];25        int x3 = min(x1, x2), y3 = min(y1, y2);26        int x4 = max(x1, x2), y4 = max(y1, y2);27        if (check(x3, y3, x4, y4)) {28          ans = max(ans, (x4 - x3) * (y4 - y3));29        }30      }31    }32    return ans;33  }34};

1class Solution:2    def maxRectangleArea(self, points: List[List[int]]) -> int: def check(x1: int, y1: int, x2: int, y2: int) -> bool: cnt = 0 for x, y in points: if x < x1 or x > x2 or y < y1 or y > y2: continue if (x == x1 or x == x2) and (y == y1 or y == y2): cnt += 1 continue return False return cnt == 4 ans = - 1 for i, (x1, y1) in enumerate(points): for x2, y2 in points[: i]: x3, y3 = min(x1, x2), min(y1, y2) x4, y4 = max(x1, x2), max(y1, y2) if check(x3, y3, x4, y4): ans = max(ans, (x4 - x3) * (y4 - y3)) return ans

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.