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 I

Number: 3681

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an array of unique points on an infinite plane, determine the maximum area of an axis-aligned rectangle that can be formed using exactly four of these points as its corners, such that the rectangle does not contain any other point (either inside or on its border). If no valid rectangle exists, return -1.

Key Insights

  • Since the points array length is at most 10, a brute-force enumeration over all combinations of four points is feasible.
  • For four points to form an axis-aligned rectangle, they must have exactly two distinct x coordinates and two distinct y coordinates.
  • Once a candidate rectangle is identified, we must ensure that no other point (beyond the four corners) lies within or on the boundary of the rectangle.
  • Calculate the area of a candidate rectangle as (max_x - min_x) * (max_y - min_y) and maintain the maximum among valid rectangles.

Space and Time Complexity

Time Complexity: O(n^5) in worst-case scenarios – O(n^4) for enumerating all quadruplets and O(n) for checking each candidate rectangle against all points, where n is the number of points (n ≤ 10). Space Complexity: O(n), mainly for storing the input points and a set for quick look-up if needed.

Solution

We use a brute-force approach to examine every combination of 4 points. For each quadruplet, first check that the points have exactly two unique x coordinates and two unique y coordinates (ensuring an axis-aligned rectangle formation). Compute the boundary (min_x, max_x, min_y, max_y) and then verify that no additional point in the input lies within or on these boundaries (except for the 4 corner points). If valid, calculate the area and update the maximum area found. Return the maximum area if a valid rectangle exists or -1 otherwise.

Code Solutions

import itertools

def maxAreaRectangle(points):
    max_area = -1
    n = len(points)
    point_set = set(map(tuple, points))  # for quick lookup

    # Iterate over all combinations of 4 points
    for quad in itertools.combinations(points, 4):
        xs = {p[0] for p in quad}
        ys = {p[1] for p in quad}
        # Check if there are exactly 2 distinct x and y coordinates
        if len(xs) != 2 or len(ys) != 2:
            continue
        
        # Determine boundaries
        min_x, max_x = min(xs), max(xs)
        min_y, max_y = min(ys), max(ys)
        candidate_corners = {(min_x, min_y), (min_x, max_y), (max_x, min_y), (max_x, max_y)}
        
        # Check if the selected 4 points exactly are the corners
        if candidate_corners != set(map(tuple, quad)):
            continue
        
        # Check if any extra point lies inside or on the border
        valid = True
        for px, py in points:
            # Skip the points that are the rectangle corners
            if (px, py) in candidate_corners:
                continue
            # If a point lies within or on the rectangle, invalidate this rectangle
            if min_x <= px <= max_x and min_y <= py <= max_y:
                valid = False
                break
        if not valid:
            continue
        
        # Calculate rectangle area
        area = (max_x - min_x) * (max_y - min_y)
        max_area = max(max_area, area)
    return max_area

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