Is Maximum Area Rectangle With Point Constraints I easy or hard?

Maximum Area Rectangle With Point Constraints I is generally classified as a medium difficulty problem. The geometric observation about diagonal corners is straightforward, but correctly validating that no extra points lie inside the rectangle requires careful implementation.

Maximum Area Rectangle With Point Constraints I Python/Java solution

The typical implementation enumerates pairs of points as diagonals, checks if the other two corners exist in a hash set, and verifies that no additional point lies inside the rectangle. This logic translates directly across Python, Java, C++, Go, and TypeScript with O(n^3) time complexity.

How to solve Maximum Area Rectangle With Point Constraints I in O(n)?

An O(n) solution is not practical because rectangles depend on relationships between multiple point pairs. The typical approach enumerates diagonal pairs and validates the rectangle, leading to O(n^3) complexity. More advanced geometric data structures like segment trees or Binary Indexed Trees may reduce checks in extended variants but are not required for the basic version.

What is the best approach for Maximum Area Rectangle With Point Constraints I?

The most practical approach is diagonal enumeration with a hash set. Treat two points as potential opposite corners of a rectangle and compute the other two corners directly. Use a set to check if those points exist and scan the input to confirm no extra points lie inside the rectangle. This reduces the search space to O(n^3) time with O(n) space.

Is Maximum Area Rectangle With Point Constraints I asked at Google/Amazon/Meta?

Geometry and coordinate-based enumeration problems similar to this appear in interviews at companies like Google, Amazon, and Meta. The exact problem may vary, but the pattern of validating rectangles using coordinate relationships and hash lookups is common in technical interviews.

What data structure is used in Maximum Area Rectangle With Point Constraints I?

A hash set is typically used to store all points for constant-time coordinate lookup. The algorithm also relies on simple geometry checks and nested iteration over the array of points to test possible rectangle diagonals.

What is the time complexity of Maximum Area Rectangle With Point Constraints I?

The common optimized enumeration approach runs in O(n^3) time and O(n) space. Two points are selected as diagonal corners, the other two corners are checked using a hash set, and the remaining points are scanned to ensure the rectangle contains no extra points.

Description Hints 3 Solution Video 11:28

3380. Maximum Area Rectangle With Point Constraints I

Medium51.1% acceptance2 companies

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.

Asked at 2 companies

UKG

Google

Topics

Hints open one at a time

Hint 1

If (x1, y1) and (x2, y2) are two opposite corners of a rectangle, then the other two would be (x1, y2) and (x2, y1).

Hint 2

Fix two points and find the other two using a set data structure.

Hint 3

After determining the rectangle, iterate through the array of points to ensure no point lies on the rectangle’s border or within its interior.

11:28

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

3380. Maximum Area Rectangle With Point Constraints I

Asked at 2 companies

Topics

Hints open one at a time

Similar problems