3380. Maximum Area Rectangle With Point Constraints I

MediumBinary Indexed TreeSegment TreeGeometryArrayMathEnumerationSorting

Problem Description

You are given an array points where each 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.

Intuition

To solve this problem, we take advantage of the key condition that the rectangle's edges are parallel to the axes. This simplifies checking for candidate rectangles since we only need to check for opposite corners (i.e., bottom-left and top-right).

The approach involves:

Pair Selection: We begin by trying to form rectangles using two points as opposite corners (for instance, considering any point as the top-right [x_4, y_4] and bottom-left [x_3, y_3] corners of the rectangle).
Verification: For each pair of selected corners, we need to verify if the other two corners of such a rectangle are present among the given points:
- Check if points exist for (x_3, y_4) and (x_4, y_3), thereby forming the remaining corners of the rectangle.
Area Calculation: Once a valid rectangle is identified (one that has no other points inside or on its edges except the corners), compute its area as (x_4 - x_3) * (y_4 - y_3).
Maximization: Keep track of the maximum area encountered throughout this process. If no rectangle is found that meets all the conditions, return -1.

By systematically checking pairs and ensuring that only the four corner points are used, the task of finding the valid rectangles becomes feasible. This approach leverages the ordered nature of points in forming rectangles aligned with the coordinate axes, significantly reducing the complexity of checking conditions.

Learn more about Segment Tree, Math and Sorting patterns.

Solution Approach

The solution utilizes an Enumeration approach, which methodically checks potential rectangles by considering all possible pairs of points as opposite corners and then verifying if they can form valid rectangles.

Implementation Steps:

Initialization: Start with a variable ans set to -1, which will ultimately store the maximum rectangle area found.
Pair Iteration: Iterate over all pairs of points (x1, y1) and (x2, y2) from the points list. This uses a double loop where the inner loop ensures that (x2, y2) is not considered as a previous point compared to (x1, y1) to avoid redundant checks.
Determine Corners:
- For each pair (x1, y1) and (x2, y2), identify the min and max for x and y coordinates:
  - Bottom-left corner (x3, y3) is (min(x1, x2), min(y1, y2)).
  - Top-right corner (x4, y4) is (max(x1, x2), max(y1, y2)).
Validation Function check:
- Define a helper function check(x3, y3, x4, y4) to verify if a rectangle can be formed by these corners and only exactly the four required corner points are present. This involves:
  - Initializing a count cnt to tally points that coincide with the rectangle corners.
  - Iterating through each point (x, y) to ensure they either lie strictly within or outside the rectangle, or match one of its corners.
Area Calculation and Maximization:
- If the check function returns true (implying a valid rectangle), compute its area as (x4 - x3) * (y4 - y3).
- Update ans to be the maximum area found so far.
Return Result: After all pairs have been evaluated, return ans, which will be -1 if no valid rectangles were found, or the maximum area if any were viable.

The robustness of this method lies in efficiently evaluating combinations and ensuring the rigidity of conditions, allowing for streamlined calculation rather than exhaustive enumeration of all possible point combinations.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's work through a small example to illustrate the solution approach.

Suppose we are given the following points on a 2D plane:

[ points = [[1, 1], [1, 3], [3, 1], [3, 3], [2, 2]] ]

We are tasked to find the maximum area of a rectangle with edges parallel to the axes using these points, such that it contains no other points.

Step-by-Step Walkthrough:

Initialization:
- Set ans = -1 to store the maximum area found.
Pair Iteration:
- Iterate over all pairs of points:
  - Consider (1, 1) and (3, 3):
    - Identify x3 = min(1, 3) = 1, y3 = min(1, 3) = 1
    - Identify x4 = max(1, 3) = 3, y4 = max(1, 3) = 3
Determine Corners:
- Potential corners for a rectangle are (1, 1) and (3, 3). We now need to check for (1, 3) and (3, 1) to form a valid rectangle.
Validation Function check:
- Check if points (1, 3) and (3, 1) exist in the list:
  - Both points are present, thus forming a rectangle.
- Verify no other points are inside or on the edges except these corners.
Area Calculation and Maximization:
- Compute the area of this rectangle as ((3 - 1) \times (3 - 1) = 4).
- Update ans = max(-1, 4) = 4.
Additional Checks:
- Iterate through other pairs such as (1, 1) and (1, 3) or (3, 1) and (3, 3), which are lines or degenerate shapes, hence ignored.
Return Result:
- After checking all pairs, the maximum area found is (4).

Thus, the maximum area of a rectangle that can be formed is 4.

This example clearly shows how the method efficiently processes all point pairs to determine possible rectangles and calculate their areas, adhering to the conditions provided.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxRectangleArea(self, points: List[List[int]]) -> int:
5        # Function to check if four points form a valid rectangle
6        def check(x1: int, y1: int, x2: int, y2: int) -> bool:
7            count = 0
8            for x, y in points:
9                # Skip points that are outside the boundary of the rectangle
10                if x < x1 or x > x2 or y < y1 or y > y2:
11                    continue
12                # Check if the point is a vertex of the rectangle
13                if (x == x1 or x == x2) and (y == y1 or y == y2):
14                    count += 1
15                    continue
16                # If any point is inside the boundary but not a vertex, return False
17                return False
18            # Check if exactly four points are vertices of the rectangle
19            return count == 4
20
21        max_area = -1
22        # Iterate over each pair of points to consider them as diagonal vertices of a rectangle
23        for i, (x1, y1) in enumerate(points):
24            for x2, y2 in points[:i]:
25                # Determine the opposite diagonal corners
26                x3, y3 = min(x1, x2), min(y1, y2)
27                x4, y4 = max(x1, x2), max(y1, y2)
28                # Check if a valid rectangle can be formed
29                if check(x3, y3, x4, y4):
30                    # Calculate and update the maximum rectangle area
31                    max_area = max(max_area, (x4 - x3) * (y4 - y3))
32        return max_area
33

1import java.util.List;
2
3class Solution {
4    public int maxRectangleArea(int[][] points) {
5        int maxArea = -1; // Variable to store the maximum area found
6      
7        // Iterate over each pair of points to check the possibility of forming a rectangle
8        for (int i = 0; i < points.length; ++i) {
9            int x1 = points[i][0], y1 = points[i][1];
10          
11            for (int j = 0; j < i; ++j) {
12                int x2 = points[j][0], y2 = points[j][1];
13              
14                // Define possible rectangle corners (x3, y3) and (x4, y4)
15                int x3 = Math.min(x1, x2), y3 = Math.min(y1, y2);
16                int x4 = Math.max(x1, x2), y4 = Math.max(y1, y2);
17              
18                // Check if a rectangle can be formed with these points
19                if (check(points, x3, y3, x4, y4)) {
20                    // Calculate the area and update maxArea if it's the largest found
21                    maxArea = Math.max(maxArea, (x4 - x3) * (y4 - y3));
22                }
23            }
24        }
25        return maxArea; // Return the maximum rectangle area found, or -1 if none
26    }
27
28    // Helper method to verify if a rectangle can be formed with corners (x1, y1) and (x2, y2)
29    private boolean check(int[][] points, int x1, int y1, int x2, int y2) {
30        int cornerCount = 0; // Counter to verify four corners exist
31      
32        for (int[] point : points) {
33            int x = point[0];
34            int y = point[1];
35          
36            // If point is outside potential rectangle corners, continue
37            if (x < x1 || x > x2 || y < y1 || y > y2) {
38                continue;
39            }
40
41            // Check if the point is one of the corners of the rectangle
42            if ((x == x1 || x == x2) && (y == y1 || y == y2)) {
43                cornerCount++; // Increment corner count
44                continue;
45            }
46            return false; // If point is within bounds but not a corner, return false
47        }
48        return cornerCount == 4; // Return true only if exactly four corners are found
49    }
50}
51

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    int maxRectangleArea(std::vector<std::vector<int>>& points) {
7        // Helper function to check if the rectangle defined by (x1, y1) and (x2, y2) has exactly four corners from points
8        auto check = [&](int x1, int y1, int x2, int y2) -> bool {
9            int cornerCount = 0; 
10            for (const auto& point : points) {
11                int x = point[0];
12                int y = point[1];
13                // If point is outside the rectangle, skip
14                if (x < x1 || x > x2 || y < y1 || y > y2) {
15                    continue;
16                }
17                // Increase count for points that lie on the corners of the rectangle
18                if ((x == x1 || x == x2) && (y == y1 || y == y2)) {
19                    cornerCount++;
20                    continue;
21                }
22                // If a point is inside the rectangle but not a corner, return false
23                return false;
24            }
25            // A valid rectangle needs exactly four corner points
26            return cornerCount == 4;
27        };
28
29        int maxArea = -1;
30        int n = points.size();
31
32        // Iterate through each pair of points to consider each as potential opposing corners of rectangles
33        for (int i = 0; i < n; ++i) {
34            int x1 = points[i][0];
35            int y1 = points[i][1];
36            for (int j = 0; j < i; ++j) {
37                int x2 = points[j][0];
38                int y2 = points[j][1];
39              
40                // Define potential top-left and bottom-right corners of the rectangle
41                int minX = std::min(x1, x2);
42                int minY = std::min(y1, y2);
43                int maxX = std::max(x1, x2);
44                int maxY = std::max(y1, y2);
45
46                // If valid rectangle, calculate area and update maximum area
47                if (check(minX, minY, maxX, maxY)) {
48                    int area = (maxX - minX) * (maxY - minY);
49                    maxArea = std::max(maxArea, area);
50                }
51            }
52        }
53      
54        // Return the maximum area found, or -1 if no rectangle was valid
55        return maxArea;
56    }
57};
58

1// Function to calculate the maximum rectangle area formed by given points
2function maxRectangleArea(points: number[][]): number {
3  
4    // Helper function to check if a rectangle's corners are among the points
5    const check = (x1: number, y1: number, x2: number, y2: number): boolean => {
6        let cornerCount = 0; // Counter for the number of corners found among the points
7
8        for (const point of points) {
9            const [x, y] = point;
10
11            // Skip if the point is outside the rectangle bounds
12            if (x < x1 || x > x2 || y < y1 || y > y2) {
13                continue;
14            }
15
16            // Check if the point is a corner of the rectangle
17            if ((x === x1 || x === x2) && (y === y1 || y === y2)) {
18                cornerCount++;
19                continue;
20            }
21          
22            // If a point is inside the rectangle but not a corner, return false
23            return false;
24        }
25
26        // Valid rectangle if all four corners are identified
27        return cornerCount === 4;
28    };
29
30    let maxArea = -1; // Initialize maximum area to a negative value
31
32    // Iterate through each pair of points to potentially define rectangle corners
33    for (let i = 0; i < points.length; i++) {
34        const [x1, y1] = points[i];
35
36        for (let j = 0; j < i; j++) {
37            const [x2, y2] = points[j];
38
39            // Determine the bottom-left and top-right corners of the rectangle
40            const [x3, y3] = [Math.min(x1, x2), Math.min(y1, y2)];
41            const [x4, y4] = [Math.max(x1, x2), Math.max(y1, y2)];
42          
43            // Check if the rectangle is formed by the given points
44            if (check(x3, y3, x4, y4)) {
45                // Calculate and compare the area with the current maximum
46                maxArea = Math.max(maxArea, (x4 - x3) * (y4 - y3));
47            }
48        }
49    }
50
51    return maxArea; // Return the largest area found
52}
53

Time and Space Complexity

The time complexity of the code is O(n^3). This is because the outer loop iterates over each point with O(n) complexity, and the inner loop, also iterating over points, adds another O(n), making it O(n^2). Additionally, for each combination of two points, we invoke the check function which iterates over all points, adding another O(n). Thus, the total time complexity is O(n^3).

The space complexity of the code is O(1). No additional data structures are used that scale with the input size n, meaning the space complexity remains constant.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the following problems can be solved with backtracking (select multiple)

Generating subsets

Generating random numbers

Generating permutations

Sorting integers