Solution: Maximum Area Rectangle With Point Constraints I

Statement

You are given an array of points, where points[i] have two values: $[x_i, y_i]$, representing its position on a flat plane.

Your goal is to find the largest rectangle (having maximum area) that can be formed using any four points as the corners. The rectangle should meet the following conditions:

• It has its borders parallel to the axes.

• It should not contain any other points inside or along its border.

Return the area of the largest rectangle you can create. If no such rectangle can be formed, return $-1$.

Constraints:

• $1 \leq$ points.length $\leq 10$

• points[i].length $= 2$

• $0 \leq x_i, y_i \leq 100$

• All the given points are unique.

Solution

This problem is finding the largest rectangle that can be formed using given points on a 2D plane. The main challenge is to figure out how to identify rectangles using the points and calculate their areas efficiently. Rectangles follow specific rules, like having opposite corners connected by diagonal lines and straight edges aligned with the coordinate axes. This makes the math and geometry pattern the perfect approach for solving this problem. By focusing on how points are positioned relative to one another and using coordinate-based logic to validate rectangle formation, we aim to maximize the area while adhering to strict geometric constraints.

We start by storing the list of points in a set for efficient look-ups. Then, we iterate through all unique pairs of points to find diagonally opposite corners of potential rectangles. For each pair, we check if the other two corners of the rectangle exist in the set of points. If the other two corners exist, we check that the rectangle is valid by ensuring the points for a proper rectangle (aligned edges, no irregular shapes). We also ensure no points lie on the edges or inside the rectangle except its four corners. If the rectangle is valid, we calculate its area and return the maximum valid area found. Otherwise, we return $-1$.

Following are the detailed steps of the algorithm:

1. We start by initializing a set, pointSet, for quick look-ups. This also helps efficiently validate the existence of the rectangle’s other two corners (x1, y2) and (x2, y1).

2. We also initialize a variable, maxArea = -1, to store the largest valid rectangle’s area. If no valid rectangle is found, we return $-1$.

3. We iterate over all the unique pairs of points using nested for loops where, in the outer loop, we select the first point (x1, y1), and in the inner loop, we select the second point (x2, y2):

   1. If two points lie on the same horizontal or vertical line (i.e., x1 == x2 or y1 == y2), they can not form a rectangle, so we skip them.

   2. The other two corners, (x1, y2) and (x2, y1), must exist in pointSet for a valid rectangle. If either corner is missing, the pair is skipped. Otherwise, we do the following:

      1. We calculate the rectangle’s boundaries by finding the minimum and maximum x and y values:

         1. xMin = min(x1, x2)

         2. xMax = max(x1, x2)

         3. yMin = min(y1, y2)

         4. yMax = max(y1, y2)

      2. We create a boolean variable, valid, to confirm the rectangle’s validity.

      3. We iterate over the points array, and for each point (px, py):

         1. We skip the point if it is one of the rectangle’s four corners (x1, y1), (x2, y2), (x1, y2), or (x2, y1). These points are allowed because they are part of the rectangle’s boundary.

         2. Otherwise, we use a helper function, insideOrBorderRectangle, to check if a point (px, py) lies inside or on the border of the rectangle defined by the corners (xMin, yMin) and (xMax, yMax):

            1. If it does, we set valid to FALSE and terminate this iteration here.

      4. If the rectangle is valid:

         1. We calculate the area as the distance between x-coordinates, abs(x2 - x1), multiplied by the distance between y-coordinates, abs(y2 - y1).

         2. If this area is larger than the previous maximum area, we update maxArea.

4. After all pairs of points are checked, the largest valid rectangle area (maxArea) is found, so we return it. If no valid rectangle is found, we return $-1$.

Let’s look at the following illustration to get a better understanding of the solution: