#3380

Medium

LeetCode Problem Workspace

Maximum Area Rectangle With Point Constraints I

Find the maximum area of a rectangle formed by given points on a plane with unique coordinates.

array math binary indexed tree segment tree geometry

Problem Statement

You are given an array of points, where each point is represented as [xi, yi] and indicates a coordinate on an infinite 2D plane. Your goal is to find the maximum area of a rectangle that can be formed using these points as the four corners of the rectangle.

If it is not possible to form a rectangle with the given points, return -1. The challenge involves checking for valid rectangle configurations and calculating the area, making use of mathematical relationships between point coordinates.

Examples

Example 1

Input: points = [[1,1],[1,3],[3,1],[3,3]]

Output: 4

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

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

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 <= xi, yi <= 100
All the given points are unique.

Solution Approach

Brute Force Method

A simple brute force approach is to check every possible combination of four points and determine if they form a rectangle. If so, calculate the area and update the maximum found. This involves using the properties of rectangles and checking if opposite corners have the correct coordinates to form the other two corners.

Efficient Search with Hashing

Using a hash set to store the points can significantly speed up the search. For every pair of points, check if the other two necessary points to complete the rectangle exist. If they do, calculate the area and keep track of the maximum.

Mathematical Optimization

The optimal solution leverages the mathematical property that for two opposite corners of a rectangle (x1, y1) and (x2, y2), the other two corners will be (x1, y2) and (x2, y1). Using this property, we can efficiently search for valid rectangles and calculate their areas.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The brute force method has a time complexity of O(n^4), as it checks all possible combinations of points. The hashing approach reduces the time complexity to O(n^2) by utilizing fast lookups. The mathematical optimization can further improve this by reducing redundant calculations, but the exact complexity depends on the specific implementation details and optimizations applied.

What Interviewers Usually Probe

The problem involves array manipulation and geometric reasoning.
Candidates should demonstrate understanding of how to leverage math for optimizations.
Understanding of time and space complexities when applying different solutions is crucial.

Common Pitfalls or Variants

Common pitfalls

Incorrectly assuming that four points will always form a rectangle. The points need to align properly to form a valid rectangle.
Overlooking edge cases where no rectangle can be formed, leading to an incorrect return value of 0 instead of -1.
Inefficient solutions that do not make use of hashing or mathematical properties, leading to unnecessarily high time complexity.

Follow-up variants

Generalize to find rectangles of different orientations, not just axis-aligned ones.
Extend the problem to work with a larger set of points and optimize the algorithm for larger input sizes.
Modify the problem to find the minimum area instead of the maximum.

FAQ

What is the main algorithmic pattern for the Maximum Area Rectangle With Point Constraints I?

The problem primarily involves array manipulation combined with geometric reasoning and mathematical optimizations to identify valid rectangles.

How do you efficiently find if four points form a rectangle?

You can use a hashing approach to store points and check for valid rectangles by comparing pairs of points and verifying that the other two points exist to complete the rectangle.

What is the complexity of the brute force solution for the Maximum Area Rectangle With Point Constraints I?

The brute force solution has a time complexity of O(n^4) as it checks every combination of four points.

Why do you need to check for opposite corners in this problem?

Checking for opposite corners is essential because it ensures that the points form a valid rectangle by guaranteeing the other two corners' coordinates are correct.

What are some common pitfalls in solving Maximum Area Rectangle With Point Constraints I?

Some common pitfalls include incorrectly assuming that four points will always form a rectangle, overlooking edge cases where no rectangle can be formed, and using inefficient solutions that don't leverage mathematical optimizations.

terminal

Solution

Solution 1: Enumeration

We can enumerate the bottom-left corner $(x_3, y_3)$ and the top-right corner $(x_4, y_4)$ of the rectangle. Then, we enumerate all points $(x, y)$ and check if the point is inside or on the boundary of the rectangle. If it is, it does not meet the condition. Otherwise, we exclude the points outside the rectangle and check if there are 4 remaining points. If there are, these 4 points can form a rectangle. We calculate the area of the rectangle and take the maximum value.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    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

Continue Practicing

#3382 maximum area rectangle with point constraints ii #3027 find the number of ways to place people ii #3025 find the number of ways to place people i