We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Area Rectangle With Point Constraints II

Number: 3689

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given n unique 2D points (with x‑ and y‑coordinates provided by the arrays xCoord and yCoord), find the maximum area of an axis‐aligned rectangle whose 4 corners come from these points and that does not have any other point (from the given set) either inside or on its border. If no such rectangle exists, return -1.

Key Insights

  • The rectangle must have its sides parallel to the x‑ and y‑axes. Thus it is uniquely determined by two distinct x coordinates and two distinct y coordinates.
  • A candidate rectangle is “empty” if the only points from the set with coordinates in [x1, x2] and [y1, y2] are its four vertices.
  • A brute‐force over every quadruple is infeasible given n can be up to 2×10^5.
  • A useful idea is to “group by” x coordinate. For a fixed x, sort its y coordinates.
    • For any adjacent pair of points in this sorted order, there is no other point (in that column) between them – they form a candidate vertical “segment.”
  • For a vertical segment (with y coordinates yLow and yHigh) in one column, if the same vertical segment appears in another column, they can form the left and right boundaries of a rectangle.
    • However, the candidate rectangle is valid only if there are no extra points along the horizontal boundaries (i.e. at yLow or yHigh between the two x values).
  • By also pre‐grouping by y coordinate (mapping y to a sorted list of x values), one can perform binary searches to quickly check whether any unwanted points lie on the horizontal boundaries.
  • This “group‐by‐column then by segment” approach reduces the number of candidate rectangles substantially and makes it possible to check the emptiness condition efficiently.

Space and Time Complexity

Time Complexity: O(m * k² * log n), where m is the number of unique x coordinates and k is the average number of points per column. In the worst‐case (with heavy coordinate collisions) additional optimizations (or advanced data structures like 2D BIT/Segment Tree) may be needed to keep the solution efficient. Space Complexity: O(n), to store the point set and the mappings by x and by y.

Solution

The solution uses two main data structures:

  1. A dictionary mapping each unique x coordinate to the sorted list of y coordinates for that column.
  2. A dictionary mapping each unique y coordinate to the sorted list of x coordinates having that y coordinate.

Steps: • Preprocess the points into the two dictionaries. • For each unique x coordinate, examine consecutive y pairs (since these “vertical segments” have no intermediate point in that column). • For a given vertical segment (yLow, yHigh), record the x coordinate in a mapping from (yLow, yHigh) to a list of x’s where this segment exists. • For every vertical segment that appears in more than one column, iterate over adjacent pairs of x values in its x‑list. For each candidate rectangle between two x boundaries, use the dictionary keyed by y to binary search the horizontal boundary rows.
 – For the bottom edge (yLow) and top edge (yHigh), ensure that there is no point with that y on any column strictly between the two x boundaries. • If the horizontal boundaries are “clean” then compute the area and update the maximum. • Finally, return the maximum area found or -1 if none is valid.

The “gotcha” is the border check: Even if the four corner points exist, an extra point lying on (for example) yLow (or yHigh) between the two x coordinates would invalidate the rectangle. Using the grouping-by-y dictionary helps check these in O(log n) time per boundary.

The following code solutions in Python, JavaScript, C++ and Java illustrate this step‐by‐step with detailed inline comments.

Code Solutions

# Python solution
def maxAreaRectangle(xCoord, yCoord):
    from collections import defaultdict
    import bisect

    n = len(xCoord)
    # Build a set for complete point lookup if needed later (not used in this approach)
    points = set((xCoord[i], yCoord[i]) for i in range(n))
    
    # Group by x: map each x coordinate to a sorted list of its y coordinates.
    x_to_y = defaultdict(list)
    for i in range(n):
        x_to_y[xCoord[i]].append(yCoord[i])
    for x in x_to_y:
        x_to_y[x].sort()

    # Group by y: map each y coordinate to a sorted list of its x coordinates.
    y_to_x = defaultdict(list)
    for i in range(n):
        y_to_x[yCoord[i]].append(xCoord[i])
    for y in y_to_x:
        y_to_x[y].sort()
    
    # For every x, for every consecutive y pair, record the vertical segment (yLow, yHigh) where yLow < yHigh.
    seg_to_x_list = defaultdict(list)
    for x, ys in x_to_y.items():
        # Only consider adjacent pairs in sorted order since extra interior point in the column will violate emptiness.
        for i in range(len(ys)-1):
            yLow = ys[i]
            yHigh = ys[i+1]
            seg_to_x_list[(yLow, yHigh)].append(x)

    max_area = -1
    # For each vertical segment that appears on multiple x columns, try to form candidate rectangles.
    for (yLow, yHigh), x_list in seg_to_x_list.items():
        # sort the list of x coordinates for this segment
        x_list.sort()
        # Try each adjacent pair in x_list to form rectangle candidate boundaries
        for i in range(len(x_list)-1):
            x_left = x_list[i]
            x_right = x_list[i+1]
            width = x_right - x_left
            height = yHigh - yLow
            area = width * height
            # Check horizontal boundaries for extra points.
            valid = True
            # For the bottom boundary yLow: ensure no extra x exists strictly between x_left and x_right
            x_candidates = y_to_x[yLow]
            left_index = bisect.bisect_right(x_candidates, x_left)
            if left_index < len(x_candidates) and x_candidates[left_index] < x_right:
                valid = False
            
            # For the top boundary yHigh: ensure no extra x exists strictly between x_left and x_right
            if valid:
                x_candidates = y_to_x[yHigh]
                left_index = bisect.bisect_right(x_candidates, x_left)
                if left_index < len(x_candidates) and x_candidates[left_index] < x_right:
                    valid = False
            
            if valid:
                max_area = max(max_area, area)
    
    return max_area

# Example usage:
print(maxAreaRectangle([1,1,3,3], [1,3,1,3]))   # Expected output: 4
print(maxAreaRectangle([1,1,3,3,2], [1,3,1,3,2])) # Expected output: -1
print(maxAreaRectangle([1,1,3,3,1,3], [1,3,1,3,2,2])) # Expected output: 2
← Back to All Questions