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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Area Rectangle With Point Constraints I

Difficulty: Medium

Problem Description

You are given an array points where points[i] = [xi, yi] 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.

Key Insights

  • The rectangle is defined by selecting any two points as opposite corners.
  • The other two corners can be determined using the x and y coordinates of the selected points.
  • We must check that no other point lies inside or on the border of the rectangle formed by the selected corners.
  • The area of the rectangle can be computed as (width * height), where width and height are the distances between the x and y coordinates of the corners.

Space and Time Complexity

Time Complexity: O(n^4) - Since we need to check combinations of four points. Space Complexity: O(n) - To store the points in a set for quick lookup.

Solution

To solve this problem, we will:

  1. Store all points in a set for O(1) lookup.
  2. Iterate through all combinations of two points to consider them as opposite corners of a rectangle.
  3. For each pair, determine the other two corners needed to complete the rectangle.
  4. Check if any point lies inside or on the border of the rectangle using the set.
  5. Calculate the area if the rectangle is valid and keep track of the maximum area found.

Code Solutions

def maxArea(points):
    point_set = set(map(tuple, points))
    max_area = -1
    
    for i in range(len(points)):
        for j in range(i + 1, len(points)):
            x1, y1 = points[i]
            x2, y2 = points[j]
            
            # Check if they can form a rectangle
            if x1 != x2 and y1 != y2:
                # Determine the other two corners
                bottom_left = (x1, y2)
                top_right = (x2, y1)
                
                # Check if the other two corners exist
                if bottom_left in point_set and top_right in point_set:
                    # Check if any point is inside or on the border
                    area = abs(x2 - x1) * abs(y2 - y1)
                    valid = True
                    
                    for x, y in points:
                        if (x1 <= x <= x2) and (y1 <= y <= y2) and (x, y) not in {points[i], points[j], bottom_left, top_right}:
                            valid = False
                            break
                    
                    if valid:
                        max_area = max(max_area, area)
    
    return max_area
← Back to All Questions