LeetCode Problem 3380

Difficulty: 🟡 Medium
Topics: Array, Math, Binary Indexed Tree, Segment Tree, Geometry, Sorting, Enumeration

Solution

LeetCode 3380 - Maximum Area Rectangle With Point Constraints I

Problem Understanding

The problem gives us a set of unique points on a 2D plane. We need to determine the largest possible axis-aligned rectangle that can be formed using exactly four of those points as its corners.

An axis-aligned rectangle means:

• The rectangle's sides must be parallel to the x-axis and y-axis.

• If (x1, y1) and (x2, y2) are opposite corners, then the other two corners must be:

• (x1, y2)

• (x2, y1)

However, there is an additional and very important constraint. The rectangle is only valid if no other point lies:

• strictly inside the rectangle, or
• on any of its borders

The only points allowed on the border are the four corner points themselves.

The input is an array points, where each element is a coordinate pair [x, y]. All points are guaranteed to be unique.

The output should be:

• the maximum rectangle area among all valid rectangles
• -1 if no valid rectangle exists

The constraints are extremely small:

• 1 <= points.length <= 10

This immediately tells us that exponential or high polynomial solutions are acceptable. With only 10 points, brute force enumeration becomes feasible.

A few important edge cases stand out immediately.

If there are fewer than four points, forming a rectangle is impossible. The answer must be -1.

Another tricky case occurs when the four rectangle corners exist, but an additional point lies somewhere on an edge or inside the rectangle. Even though the rectangle geometrically exists, it becomes invalid.

We also need to be careful not to count degenerate rectangles where width or height is zero. Two opposite corners must have different x-coordinates and different y-coordinates.

Approaches

Brute Force Approach

The most direct approach is to examine every possible set of four points and determine whether they form a valid rectangle.

For each group of four points, we can:

1. Check whether they form an axis-aligned rectangle.
2. Verify that the rectangle contains exactly those four points on its boundary.
3. Compute the area.
4. Track the maximum valid area.

This approach is correct because it explicitly checks every possible rectangle candidate.

However, identifying whether four arbitrary points form a rectangle requires additional geometric validation logic. While the input size is tiny enough that this still works, the implementation becomes unnecessarily complicated.

Optimized Enumeration Approach

A cleaner approach is based on choosing diagonal corners.

For an axis-aligned rectangle:

• if (x1, y1) and (x2, y2) are opposite corners,

• then the remaining corners must be:

• (x1, y2)

• (x2, y1)

This observation allows us to enumerate pairs of points as potential diagonals.

For every pair of points:

1. Ensure both x and y coordinates differ.
2. Compute the other two required corners.
3. Check whether those corners exist in the point set.
4. If they do, verify that no additional point lies inside or on the rectangle boundary.
5. Compute the area.

This reduces the geometric complexity significantly and leads to a much simpler implementation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^4)	O(1)	Enumerates all groups of four points
Optimal	O(n^3)	O(n)	Enumerates diagonal pairs and validates rectangles

Even though both are perfectly acceptable for n <= 10, the diagonal-based method is cleaner and easier to reason about.

Algorithm Walkthrough

1. Store all points inside a hash set.

We use a hash set because we need constant-time lookup to determine whether a corner exists. Each point is stored as a tuple (x, y). 2. Enumerate every pair of points.

Each pair is treated as a potential diagonal of a rectangle. 3. Skip invalid diagonal pairs.

If two points share the same x-coordinate or the same y-coordinate, they cannot form opposite corners of a rectangle with positive area. 4. Construct the remaining two corners.

Suppose the diagonal points are:

• (x1, y1)
• (x2, y2)

Then the other two corners must be:

• (x1, y2)
• (x2, y1)

5. Check whether both corners exist.

If either corner is missing, then the rectangle cannot be formed. 6. Determine rectangle boundaries.

Compute:

• left = min(x1, x2)
• right = max(x1, x2)
• bottom = min(y1, y2)
• top = max(y1, y2)

7. Validate the rectangle.

Iterate through every point in the input.

For each point:

• check whether it lies inside or on the border of the rectangle
• if it is one of the four corners, it is allowed
• otherwise, the rectangle becomes invalid immediately

8. Compute the area.

If the rectangle is valid:

• area = (right - left) * (top - bottom)

Update the maximum area. 9. Return the result.

If no valid rectangle was found, return -1.

Why it works

The algorithm considers every possible pair of diagonal corners. Every axis-aligned rectangle is uniquely determined by its diagonally opposite corners, so no valid rectangle can be missed.

For every candidate rectangle, we explicitly verify:

• all four corners exist
• no extra point lies inside or on the boundary

Therefore, every accepted rectangle satisfies the problem constraints, and the maximum valid area is correctly returned.

Python Solution

from typing import List

class Solution:
    def maxRectangleArea(self, points: List[List[int]]) -> int:
        point_set = set((x, y) for x, y in points)

        n = len(points)
        max_area = -1

        for i in range(n):
            x1, y1 = points[i]

            for j in range(i + 1, n):
                x2, y2 = points[j]

                # Must form a proper diagonal
                if x1 == x2 or y1 == y2:
                    continue

                corner1 = (x1, y2)
                corner2 = (x2, y1)

                # Both remaining corners must exist
                if corner1 not in point_set or corner2 not in point_set:
                    continue

                left = min(x1, x2)
                right = max(x1, x2)
                bottom = min(y1, y2)
                top = max(y1, y2)

                corners = {
                    (x1, y1),
                    (x2, y2),
                    corner1,
                    corner2,
                }

                valid = True

                for px, py in points:
                    inside_x = left <= px <= right
                    inside_y = bottom <= py <= top

                    if inside_x and inside_y:
                        if (px, py) not in corners:
                            valid = False
                            break

                if valid:
                    area = (right - left) * (top - bottom)
                    max_area = max(max_area, area)

        return max_area

The implementation begins by converting all points into a hash set for constant-time lookup. This allows us to quickly verify whether the required rectangle corners exist.

The nested loops enumerate every pair of points as potential diagonal corners. Any pair sharing the same x-coordinate or y-coordinate is skipped because such points cannot form a rectangle with positive area.

Once a valid diagonal is found, the algorithm computes the other two corners and checks whether they exist in the point set.

The rectangle validation step is critical. We iterate through all points and determine whether each point lies within the rectangle boundaries. If a point is inside or on the border and is not one of the four corners, the rectangle is invalidated.

Finally, the rectangle area is computed and used to update the running maximum.

Go Solution

package main

func maxRectangleArea(points [][]int) int {
	pointSet := make(map[[2]int]bool)

	for _, p := range points {
		pointSet[[2]int{p[0], p[1]}] = true
	}

	n := len(points)
	maxArea := -1

	for i := 0; i < n; i++ {
		x1, y1 := points[i][0], points[i][1]

		for j := i + 1; j < n; j++ {
			x2, y2 := points[j][0], points[j][1]

			// Must form a valid diagonal
			if x1 == x2 || y1 == y2 {
				continue
			}

			corner1 := [2]int{x1, y2}
			corner2 := [2]int{x2, y1}

			if !pointSet[corner1] || !pointSet[corner2] {
				continue
			}

			left := min(x1, x2)
			right := max(x1, x2)
			bottom := min(y1, y2)
			top := max(y1, y2)

			corners := map[[2]int]bool{
				[2]int{x1, y1}: true,
				[2]int{x2, y2}: true,
				corner1:        true,
				corner2:        true,
			}

			valid := true

			for _, p := range points {
				px, py := p[0], p[1]

				insideX := left <= px && px <= right
				insideY := bottom <= py && py <= top

				if insideX && insideY {
					if !corners[[2]int{px, py}] {
						valid = false
						break
					}
				}
			}

			if valid {
				area := (right - left) * (top - bottom)

				if area > maxArea {
					maxArea = area
				}
			}
		}
	}

	return maxArea
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

The Go implementation follows the same logic as the Python solution. Since Go does not support tuple keys directly, fixed-size arrays of length two are used as map keys for representing points.

The rectangle corner set is also implemented using a map with boolean values for fast membership checks.

Integer overflow is not a concern because coordinates are at most 100, so rectangle areas remain very small.

Worked Examples

Example 1

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

The point set is:

(1,1), (1,3), (3,1), (3,3)

Consider diagonal pair (1,1) and (3,3).

Variable	Value
corner1	(1,3)
corner2	(3,1)
left	1
right	3
bottom	1
top	3

Both missing corners exist.

Now validate all points:

Point	Inside Rectangle?	Corner?	Valid
(1,1)	Yes	Yes	OK
(1,3)	Yes	Yes	OK
(3,1)	Yes	Yes	OK
(3,3)	Yes	Yes	OK

No extra points exist.

Area:

(3 - 1) * (3 - 1) = 4

Maximum area becomes 4.

Final answer:

4

Example 2

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

Again, the rectangle corners exist.

Rectangle boundaries:

Variable	Value
left	1
right	3
bottom	1
top	3

During validation:

Point	Inside Rectangle?	Corner?
(2,2)	Yes	No

Since (2,2) lies inside the rectangle and is not a corner, the rectangle is invalid.

No other valid rectangle exists.

Final answer:

-1

Example 3

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

The large rectangle from (1,1) to (3,3) is invalid because points (1,2) and (3,2) lie on its border.

Now consider rectangle:

(1,2), (1,3), (3,2), (3,3)

Area:

(3 - 1) * (3 - 2) = 2

Validation succeeds because no additional points lie inside or on the border.

Final answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^3)	O(n^2) diagonal pairs, each validated in O(n)
Space	O(n)	Hash set storing all points

The algorithm checks every pair of points as potential diagonals, which requires O(n^2) iterations. For each candidate rectangle, we scan all points to validate the rectangle constraints, producing O(n^3) total time complexity.

Because n <= 10, this solution is extremely efficient in practice.

Test Cases

from typing import List

class Solution:
    def maxRectangleArea(self, points: List[List[int]]) -> int:
        point_set = set((x, y) for x, y in points)

        n = len(points)
        max_area = -1

        for i in range(n):
            x1, y1 = points[i]

            for j in range(i + 1, n):
                x2, y2 = points[j]

                if x1 == x2 or y1 == y2:
                    continue

                corner1 = (x1, y2)
                corner2 = (x2, y1)

                if corner1 not in point_set or corner2 not in point_set:
                    continue

                left = min(x1, x2)
                right = max(x1, x2)
                bottom = min(y1, y2)
                top = max(y1, y2)

                corners = {
                    (x1, y1),
                    (x2, y2),
                    corner1,
                    corner2,
                }

                valid = True

                for px, py in points:
                    if left <= px <= right and bottom <= py <= top:
                        if (px, py) not in corners:
                            valid = False
                            break

                if valid:
                    area = (right - left) * (top - bottom)
                    max_area = max(max_area, area)

        return max_area

sol = Solution()

assert sol.maxRectangleArea([[1,1],[1,3],[3,1],[3,3]]) == 4
# Basic valid rectangle

assert sol.maxRectangleArea([[1,1],[1,3],[3,1],[3,3],[2,2]]) == -1
# Interior point invalidates rectangle

assert sol.maxRectangleArea([[1,1],[1,3],[3,1],[3,3],[1,2],[3,2]]) == 2
# Border points invalidate larger rectangle

assert sol.maxRectangleArea([[0,0]]) == -1
# Single point cannot form rectangle

assert sol.maxRectangleArea([[0,0],[0,1],[1,0]]) == -1
# Fewer than four points

assert sol.maxRectangleArea([[0,0],[0,2],[2,0],[2,2],[1,0]]) == -1
# Extra point on border invalidates rectangle

assert sol.maxRectangleArea([[0,0],[0,1],[2,0],[2,1]]) == 2
# Small valid rectangle

assert sol.maxRectangleArea([
    [0,0],[0,4],[5,0],[5,4],
    [1,1],[1,2]
]) == -1
# Interior points invalidate large rectangle

assert sol.maxRectangleArea([
    [0,0],[0,2],[3,0],[3,2],
    [0,1],[3,1]
]) == 3
# Valid thinner rectangles remain possible

Test	Why
Basic 2x2 rectangle	Verifies standard valid rectangle
Rectangle with interior point	Ensures inside points invalidate rectangles
Rectangle with border points	Ensures border points invalidate rectangles
Single point	Confirms impossible cases return -1
Three points only	Cannot form rectangle
Extra edge point	Validates border checking
Small valid rectangle	Confirms area computation
Large rectangle with internal points	Ensures invalidation works correctly
Multiple valid rectangles	Confirms maximum valid area is selected

Edge Cases

One important edge case occurs when there are fewer than four points. Since a rectangle requires four corners, no valid rectangle can exist. The implementation naturally handles this because the nested loops never find a complete rectangle candidate, so the result remains -1.

Another subtle case happens when all four rectangle corners exist, but an additional point lies exactly on one of the rectangle edges. It is easy to mistakenly reject only strictly interior points. However, the problem explicitly forbids points on the border as well. The implementation correctly checks inclusive boundaries using <=, ensuring border points invalidate the rectangle.

A third tricky case involves multiple possible rectangles where some are invalid and others are valid. A naive implementation might stop after finding the first rectangle. Instead, this solution evaluates every possible rectangle and tracks the maximum valid area, ensuring the optimal rectangle is returned.

A final important case involves degenerate rectangles where width or height is zero. Such shapes are not valid rectangles and would incorrectly produce area zero. The implementation avoids this by skipping point pairs with matching x-coordinates or matching y-coordinates.