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

Maximum Area Rectangle With Point Constraints II is classified as Hard. The challenge comes from combining computational geometry ideas with sweep-line processing and advanced data structures like Fenwick Trees or Segment Trees.

Maximum Area Rectangle With Point Constraints II Python/Java solution

Implement the sweep-line algorithm by sorting points by x, compressing y-coordinates, and using a Fenwick Tree for range queries. Track pairs of y-values across columns to detect rectangles and compute their area. The same logic works in Python, Java, C++, and Go with O(n log n) complexity.

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

The most efficient solution uses a sweep line across sorted x-coordinates combined with a Binary Indexed Tree (Fenwick Tree). Points are processed column by column, and pairs of y-coordinates represent potential rectangle edges. Range queries verify that no invalid points violate the rectangle constraints. This approach runs in O(n log n) time and O(n) space.

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

Hard geometry and sweep-line problems with range query data structures are common in interviews at companies like Google and Meta. Variants involving rectangle detection, coordinate compression, and Fenwick Trees frequently appear in advanced algorithm rounds.

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

Binary Indexed Tree (Fenwick Tree) or Segment Tree is used to perform fast prefix or range queries over compressed y-coordinates. These structures allow checking whether points exist within a vertical interval in O(log n) time during the sweep.

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

The optimal algorithm runs in O(n log n) time due to sorting the points and performing logarithmic Fenwick Tree updates and queries. Space complexity is O(n) for coordinate compression, tracking y-pairs, and maintaining the data structure.

Description Hints 5 Video 1:14:20

3382. Maximum Area Rectangle With Point Constraints II

Q: How to solve Maximum Area Rectangle With Point Constraints II in O(n log n)?

Sort points by x-coordinate and sweep from left to right. For each column, generate pairs of y-values that could form vertical rectangle edges. Track the previous x-position where each pair appeared and use a Fenwick Tree or Segment Tree to query whether points exist in the vertical interval between the edges. If valid, compute the rectangle area and update the maximum.

Hard24.0% acceptance2 companies

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.

Asked at 2 companies

UKG

Google

Topics

Hints open one at a time

Hint 1

Process the points by sorting them based on their x-coordinates.

Hint 2

For each x-coordinate, sort the corresponding points by y and select two consecutive points y1 and y2 (y1 < y2).

Hint 3

Identify the closest x-coordinate (greater than the current x) where some y-coordinates lie in [y1, y2].

Hint 4

Use a segment tree to efficiently locate the nearest x-coordinate.

Hint 5

Check if the points form a valid rectangle. How?

3382. Maximum Area Rectangle With Point Constraints II

Asked at 2 companies

Topics

Hints open one at a time

Similar problems