Skip to main content
Talentd

Maximum Area Rectangle With Point Constraints II - Solution & Explanation

HardArrayMathBinary Indexed TreeSegment Tree4 min readAsked at: Google, UKG
Practice this problem

Problem Statement

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 ith 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:

Example 1 diagram

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:

Example 2 diagram

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:

Example 3 diagram

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

Approach Overview

Problem Overview: You are given a set of 2D points. The goal is to form an axis-aligned rectangle using four of those points as corners while satisfying additional constraints about points that lie between them. Among all valid rectangles, return the maximum possible area.

Approach 1: Brute Force Corner Enumeration (O(n^2) to O(n^3) time, O(n) space)

Start by treating every pair of points as potential diagonal corners of a rectangle. For each pair (x1, y1) and (x2, y2), compute the other two required corners (x1, y2) and (x2, y1) and check if they exist in a hash set. After confirming the four corners exist, scan the remaining points to ensure the rectangle satisfies the constraint conditions. This approach is easy to implement but expensive because each candidate rectangle may require scanning many points. Time complexity grows quickly as the number of points increases.

Approach 2: Sweep Line with Sorting + Binary Indexed Tree (O(n log n) time, O(n) space)

The optimized approach treats the plane as vertical sweep events. First sort all points by their x-coordinate using sorting. Compress the y-coordinates so they can be indexed efficiently. As the sweep line moves from left to right, process columns of points that share the same x value.

For every pair of y-coordinates in the current column, treat them as the potential vertical edges of a rectangle. Track the last x position where this same pair of y values appeared. If the pair appeared before, a rectangle is formed between the previous column and the current column. To verify the rectangle satisfies the point constraints, query a Binary Indexed Tree (Fenwick Tree) or Segment Tree to ensure no conflicting points lie inside the vertical range between the two columns.

The key insight is that the sweep converts a 2D geometry problem into repeated range queries on compressed y indices. Fenwick tree prefix sums allow fast checks of how many points lie in a vertical interval. Each update and query runs in O(log n), producing an overall O(n log n) algorithm that scales to large inputs.

Recommended for interviews: The sweep line with Binary Indexed Tree solution is what interviewers expect for a Hard geometry problem. Brute force shows you understand rectangle construction, but the optimized approach demonstrates knowledge of array indexing tricks, coordinate compression, and efficient range queries.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Corner EnumerationO(n^2) to O(n^3)O(n)Useful for understanding rectangle formation logic or when the number of points is very small.
Sweep Line + Binary Indexed TreeO(n log n)O(n)Best for large inputs. Efficient range queries ensure rectangle constraints are checked quickly.

Video Solution

3382. Maximum Area Rectangle With Point Constraints II (Leetcode Hard) • Programming Live with Larry • 633 views views

Frequently Asked Questions

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

Ready to solve this problem?

Practice Maximum Area Rectangle With Point Constraints II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Area Rectangle