Maximum Area Rectangle With Point Constraints I

Medium

Asked by:

22 views

Topics:

Arrays

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

Example 1:

Input: points = [[1,1],[1,3],[3,1],[3,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: points = [[1,1],[1,3],[3,1],[3,3],[2,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: points = [[1,1],[1,3],[3,1],[3,3],[1,2],[3,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 <= points.length <= 10
points[i].length == 2
0 <= x_i, y_i <= 100
All the given points are unique.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible value ranges and data types of the x and y coordinates for the points?
Can the input list of points be empty or contain null values, and if so, what should be the expected behavior?
If no rectangle can be formed based on the input points, what should the function return (e.g., 0, null, an error message)?
Are there any constraints on the orientation of the rectangle (e.g., must it be aligned with the x and y axes)?
Are duplicate points allowed in the input, and if so, how should they be handled when determining the maximum area rectangle?

Brute Force Solution

Approach

To find the biggest rectangle, we'll try every possible rectangle we can make from the given points. For each potential rectangle, we'll check if it meets the requirements of the problem.

Here's how the algorithm would work step-by-step:

First, pick any two points from the list of available points. These will form the opposite corners of our potential rectangle.
Now, we need to check if this potential rectangle is valid. This means making sure there are no points inside the rectangle that aren't allowed.
If the rectangle is valid, calculate its area.
Keep track of the biggest area we've seen so far.
Repeat this process by picking every other combination of two points and creating a rectangle from them.
After trying all possible pairs of points and their rectangles, the largest area that we tracked is the answer.

Code Implementation

def max_area_rectangle_brute_force(points):
    max_area = 0
    number_of_points = len(points)

    for first_point_index in range(number_of_points):
        for second_point_index in range(first_point_index + 1, number_of_points):
            point_one = points[first_point_index]
            point_two = points[second_point_index]

            # Define the rectangle using the two points as corners.
            x_coordinates = sorted([point_one[0], point_two[0]])
            y_coordinates = sorted([point_one[1], point_two[1]])
            bottom_left = (x_coordinates[0], y_coordinates[0])
            top_right = (x_coordinates[1], y_coordinates[1])

            is_valid = True
            # Check if any point is inside the rectangle.
            for other_point in points:
                if (bottom_left[0] < other_point[0] < top_right[0] and\
                        bottom_left[1] < other_point[1] < top_right[1]):
                    is_valid = False
                    break

            if is_valid:
                # Only calculate area for valid rectangles.
                area = (top_right[0] - bottom_left[0]) * (top_right[1] - bottom_left[1])
                max_area = max(max_area, area)

    return max_area

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm iterates through all possible pairs of points, which takes O(n^2) time. For each pair, it checks if the rectangle formed by them is valid, meaning it doesn't contain any disallowed points inside. This validation step requires iterating through all n points to check if they lie within the rectangle, resulting in an O(n) operation. Therefore, the overall time complexity is O(n^2 * n) which simplifies to O(n^3).

Space Complexity

O(1) – The algorithm iterates through all pairs of points, but it doesn't store any additional data structures that scale with the input size N (where N is the number of points). It primarily uses a few variables to store the current potential rectangle's corners, area, and maximum area seen so far. These variables occupy constant space, irrespective of N. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The optimal strategy avoids checking every possible rectangle by focusing on finding the largest possible width and height that satisfy the point constraints. We efficiently determine these dimensions by sorting and clever comparisons. This eliminates a large number of unnecessary calculations.

Here's how the algorithm would work step-by-step:

First, focus on identifying the largest possible width for a valid rectangle. Sort all the points based on their x-coordinates.
Next, iterate through the sorted points, considering each point as the right edge of a potential rectangle. For each right edge, examine all points to its left as potential left edges.
For each pair of left and right edges (representing a potential width), determine the maximum possible height allowed by the points within that width. This involves checking the y-coordinates of the points.
To find the maximum allowed height, sort the points between the current left and right x-coordinates based on their y-coordinates.
Then, consider all possible pairs of top and bottom edges by checking each sorted point as the bottom edge of our height.
Now calculate the maximum rectangle area using the possible widths and their corresponding maximum heights. Save the maximum area found so far.
Return the maximum area calculated across all potential rectangles. This approach avoids brute-force checking of all possible rectangles.

Code Implementation

def maximum_area_rectangle(points):
    maximum_area = 0
    points.sort(key=lambda point: point[0])

    for right_edge_index in range(len(points)): 
        right_x = points[right_edge_index][0]

        for left_edge_index in range(right_edge_index): 
            left_x = points[left_edge_index][0]
            width = right_x - left_x

            #Consider only points with x coordinates between the left and right edge
            valid_points = [point for point in points if left_x <= point[0] <= right_x]
            valid_points.sort(key=lambda point: point[1])

            #Iterate to check top and bottom edges to find the max height
            for top_edge_index in range(len(valid_points)): 
                bottom_y = valid_points[top_edge_index][1]
                for bottom_edge_index in range(top_edge_index + 1, len(valid_points)): 
                    top_y = valid_points[bottom_edge_index][1]
                    height = top_y - bottom_y
                    area = width * height

                    #Store the max area calculated
                    maximum_area = max(maximum_area, area)

    return maximum_area

Big(O) Analysis

Time Complexity

O(n^3 log n) – Sorting the points by x-coordinate takes O(n log n). The outer loop iterates through each point as a potential right edge (O(n)). The inner loop considers each point to the left as a potential left edge (O(n)). Inside this inner loop, we sort points within the current width by their y-coordinates, which takes O(n log n) in the worst case. Therefore, the overall time complexity is dominated by the nested loops and the inner sorting, resulting in O(n * n * n log n) which simplifies to O(n^3 log n).

Space Complexity

O(N) – The algorithm sorts the points based on x-coordinates and y-coordinates, potentially creating temporary sorted arrays or modifying the input array in place, which requires O(N) auxiliary space where N is the number of points. The algorithm iterates through the sorted points and stores points between current left and right x-coordinates for height calculation. In the worst-case scenario where all points are between the current left and right edges, this requires O(N) space. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Points array is null or empty	Return 0 as no rectangle can be formed.
Points array contains fewer than 2 points	Return 0 since a rectangle needs at least two points.
All points are on the same line (horizontal or vertical)	Return 0 because a rectangle requires at least two distinct horizontal and vertical coordinates.
Points have duplicate x or y coordinates, but no true rectangle exists	The algorithm should correctly identify that no valid rectangle can be formed and return 0.
Integer overflow when calculating area	Use a larger data type (e.g., long) to store the area or check for overflow before calculating.
Points array contains points with identical coordinates	The algorithm must handle duplicate points gracefully, possibly by skipping them or treating them as a single point.
Maximum number of points leading to performance issues (O(n^2) or worse)	Optimize the algorithm to improve its time complexity, possibly by using appropriate data structures.
Points array contains negative coordinates	The solution should correctly handle negative coordinates when calculating the area of the rectangle.

Points array is null or empty

How to Handle:

Return 0 as no rectangle can be formed.

Points array contains fewer than 2 points

How to Handle:

Return 0 since a rectangle needs at least two points.

All points are on the same line (horizontal or vertical)

How to Handle:

Return 0 because a rectangle requires at least two distinct horizontal and vertical coordinates.

Points have duplicate x or y coordinates, but no true rectangle exists

How to Handle:

The algorithm should correctly identify that no valid rectangle can be formed and return 0.

Integer overflow when calculating area

How to Handle:

Use a larger data type (e.g., long) to store the area or check for overflow before calculating.

Points array contains points with identical coordinates

How to Handle:

The algorithm must handle duplicate points gracefully, possibly by skipping them or treating them as a single point.

Maximum number of points leading to performance issues (O(n^2) or worse)

How to Handle:

Optimize the algorithm to improve its time complexity, possibly by using appropriate data structures.

Points array contains negative coordinates

How to Handle:

The solution should correctly handle negative coordinates when calculating the area of the rectangle.