LeetCode 939 - Minimum Area Rectangle

LeetCode Problem 939

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Geometry, Sorting

Solution

Problem Understanding

The problem gives us a collection of distinct points on a 2D plane. Each point is represented as [x, y], where x is the horizontal coordinate and y is the vertical coordinate.

Our task is to determine the minimum possible area of an axis-aligned rectangle that can be formed using four of these points as corners. An axis-aligned rectangle means:

• Its sides must be parallel to the X-axis and Y-axis
• The rectangle cannot be rotated
• The four corners must all exist in the input

For a rectangle with corners:

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

the area is:

$\text{Area} = |x_2 - x_1| \times |y_2 - y_1|$

The goal is to return the smallest such area among all valid rectangles. If no rectangle can be formed, we return 0.

The constraints are important:

• Up to 500 points
• Coordinates can be as large as 40000
• All points are unique

Since the number of points is relatively small, algorithms around O(n²) are reasonable, but brute-force approaches around O(n³) or O(n⁴) become too expensive.

Several edge cases are important:

• There may be fewer than four points, making rectangle formation impossible.
• Points may all lie on a single line.
• Multiple rectangles may exist, and we must return the smallest area.
• Large coordinate values require careful area calculation, though standard integer arithmetic is sufficient.
• Rectangles with width or height zero are impossible because all points are unique.

Approaches

Brute Force Approach

A straightforward solution is to examine every possible combination of four points and determine whether they form a valid rectangle.

For four points to form an axis-aligned rectangle:

• There must be exactly two distinct x-coordinates
• There must be exactly two distinct y-coordinates
• All four corner combinations must exist

This works because every valid rectangle in this problem must follow that structure.

However, checking every quadruple of points is extremely expensive. With n points, there are:

$\binom{n}{4}$

possible groups of four points.

For n = 500, this becomes far too large.

Key Insight for the Optimal Solution

An axis-aligned rectangle is completely determined by two diagonal points.

Suppose we choose two points:

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

If:

• x1 != x2
• y1 != y2

then these two points can serve as opposite corners of a rectangle.

The remaining two required corners would be:

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

So instead of checking groups of four points, we can:

1. Iterate over every pair of points
2. Treat them as possible diagonals
3. Check whether the other two corners exist

A hash set allows constant-time lookup for points, making this much more efficient.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n⁴)	O(1)	Checks every combination of four points
Optimal	O(n²)	O(n)	Uses diagonal observation with hash set lookups

Algorithm Walkthrough

Optimal Algorithm

1. Store every point inside a hash set.

We need fast existence checks for arbitrary points. A hash set allows average O(1) lookup time.

Each point is stored as a tuple (x, y). 2. Initialize a variable to track the minimum area.

We can start with infinity so that any valid rectangle becomes the current best answer. 3. Iterate through every pair of points.

For each pair:

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

we check whether they can form a rectangle diagonal. 4. Skip invalid diagonals.

If either:

• x1 == x2
• y1 == y2

then the points lie on the same vertical or horizontal line, so they cannot form opposite corners of a rectangle. 5. Compute the other two required corners.

The rectangle would require:

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

6. Check whether both corners exist in the hash set.

If both points are present, then a valid rectangle exists. 7. Compute the rectangle area.

The area is:

$|x_2-x_1|\times|y_2-y_1|$

1. Update the minimum area if the new rectangle is smaller.
2. After processing all pairs:

• Return the minimum area if a rectangle was found
• Otherwise return 0

Why it works

Every axis-aligned rectangle has exactly two diagonal corners. By iterating through every pair of points, we guarantee that every possible rectangle diagonal is considered.

For any valid rectangle, the other two corners are uniquely determined. Because we check whether those corners exist in the hash set, every valid rectangle will eventually be discovered.

Since we compute the area for every valid rectangle and keep the minimum, the final answer must be the smallest possible rectangle area.

Python Solution

from typing import List

class Solution:
    def minAreaRect(self, points: List[List[int]]) -> int:
        point_set = set()

        for x, y in points:
            point_set.add((x, y))

        min_area = float("inf")
        n = len(points)

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

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

                # Cannot form a rectangle diagonal
                if x1 == x2 or y1 == y2:
                    continue

                # Check if the other two corners exist
                if (x1, y2) in point_set and (x2, y1) in point_set:
                    area = abs(x2 - x1) * abs(y2 - y1)
                    min_area = min(min_area, area)

        return 0 if min_area == float("inf") else min_area

The implementation begins by converting all points into a hash set. This is the key optimization because rectangle validation depends on fast point existence checks.

The nested loops iterate over every pair of points. Each pair is treated as a potential rectangle diagonal.

If the two points share the same x-coordinate or y-coordinate, they cannot form a diagonal of an axis-aligned rectangle, so the algorithm skips them immediately.

For valid diagonals, the code computes the two missing corners and checks whether both exist in the set. If they do, a rectangle exists and its area is computed.

The minimum area is updated whenever a smaller rectangle is found.

At the end, if no rectangle was discovered, the value remains infinity, so the algorithm returns 0.

Go Solution

package main

import "math"

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

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

	minArea := math.MaxInt32
	n := len(points)

	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]

			// Cannot form a rectangle diagonal
			if x1 == x2 || y1 == y2 {
				continue
			}

			// Check if the other two corners exist
			if pointSet[[2]int{x1, y2}] &&
				pointSet[[2]int{x2, y1}] {

				area := abs(x2-x1) * abs(y2-y1)

				if area < minArea {
					minArea = area
				}
			}
		}
	}

	if minArea == math.MaxInt32 {
		return 0
	}

	return minArea
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

The Go implementation follows the same logic as the Python version.

Because Go does not support tuples as map keys, the solution uses a fixed-size array [2]int to represent a point.

The minimum area is initialized using math.MaxInt32. If no rectangle is found, the function returns 0.

A helper abs function is included because Go does not provide an integer absolute value function in the standard library.

Worked Examples

Example 1

Input:

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

Step 1: Build Hash Set

| Point |

|---|---|

| (1,1) |

| (1,3) |

| (3,1) |

| (3,3) |

| (2,2) |

Step 2: Examine Point Pairs

Consider pair:

Point A	Point B
(1,1)	(3,3)

These can form a diagonal because:

• x-values differ
• y-values differ

Required corners:

Required Corner
(1,3)
(3,1)

Both exist in the set.

Area:

$|3-1|\times|3-1|=4$

Current minimum area becomes 4.

Now consider:

Point A	Point B
(1,3)	(3,1)

Required corners:

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

Both exist.

Area is again 4.

The point (2,2) does not help form any rectangle.

Final answer:

4

Example 2

Input:

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

Candidate Rectangles

Rectangle using x-values 1 and 3:

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

Area:

$(3-1)\times(3-1)=4$

Rectangle using x-values 3 and 4:

Corners
(3,1)
(3,3)
(4,1)
(4,3)

Area:

$(4-3)\times(3-1)=2$

The minimum area is 2.

Final answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Every pair of points is examined once
Space	O(n)	Hash set stores all points

The dominant operation is the nested loop over point pairs. With n points, there are approximately:

$\frac{n(n-1)}{2}$

pairs to examine.

Each lookup inside the hash set is average O(1), so the overall complexity remains O(n²).

The space complexity is O(n) because all points are stored in the hash set.

Test Cases

from typing import List

class Solution:
    def minAreaRect(self, points: List[List[int]]) -> int:
        point_set = set()

        for x, y in points:
            point_set.add((x, y))

        min_area = float("inf")
        n = len(points)

        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

                if (x1, y2) in point_set and (x2, y1) in point_set:
                    area = abs(x2 - x1) * abs(y2 - y1)
                    min_area = min(min_area, area)

        return 0 if min_area == float("inf") else min_area

solution = Solution()

assert solution.minAreaRect(
    [[1,1],[1,3],[3,1],[3,3],[2,2]]
) == 4  # Basic rectangle example

assert solution.minAreaRect(
    [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
) == 2  # Multiple rectangles, choose minimum

assert solution.minAreaRect(
    [[1,1],[2,2],[3,3]]
) == 0  # No rectangle possible

assert solution.minAreaRect(
    [[0,0],[0,1],[1,0],[1,1]]
) == 1  # Smallest possible rectangle

assert solution.minAreaRect(
    [[0,0],[0,2],[3,0],[3,2]]
) == 6  # Single rectangle

assert solution.minAreaRect(
    [[1,1],[1,4],[5,1],[5,4],[2,2],[3,3]]
) == 12  # Extra points should not interfere

assert solution.minAreaRect(
    [[0,0],[0,100],[100,0],[100,100]]
) == 10000  # Large coordinates

assert solution.minAreaRect(
    [[1,1]]
) == 0  # Too few points

assert solution.minAreaRect(
    [[1,1],[1,2],[2,1]]
) == 0  # Missing fourth corner

assert solution.minAreaRect(
    [[0,0],[0,3],[4,0],[4,3],[0,1],[4,1]]
) == 4  # Multiple vertical alignments

Test	Why
[[1,1],[1,3],[3,1],[3,3],[2,2]]	Verifies standard rectangle detection
[[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]	Ensures smallest rectangle is selected
[[1,1],[2,2],[3,3]]	Tests no rectangle case
[[0,0],[0,1],[1,0],[1,1]]	Validates minimum possible area
[[0,0],[0,2],[3,0],[3,2]]	Tests a single large rectangle
[[1,1],[1,4],[5,1],[5,4],[2,2],[3,3]]	Confirms irrelevant points are ignored
[[0,0],[0,100],[100,0],[100,100]]	Tests large coordinate handling
[[1,1]]	Tests insufficient points
[[1,1],[1,2],[2,1]]	Tests missing corner scenario
[[0,0],[0,3],[4,0],[4,3],[0,1],[4,1]]	Tests multiple candidate rectangles

Edge Cases

No Rectangle Exists

A common edge case occurs when the points never form four valid rectangle corners. For example:

[[1,1],[2,2],[3,3]]

All points lie diagonally, so no axis-aligned rectangle can exist.

A buggy implementation might incorrectly assume any four points can form a rectangle. This solution avoids that issue by explicitly checking whether the two required corners exist.

If no rectangle is ever found, min_area remains infinity and the algorithm correctly returns 0.

Points Share the Same Row or Column

Pairs of points that share the same x-coordinate or y-coordinate cannot serve as rectangle diagonals.

For example:

(1,1), (1,3)

These points form a vertical line segment, not a diagonal.

Without the condition:

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

the algorithm could incorrectly attempt to compute degenerate rectangles with zero area.

Multiple Rectangles Exist

The input may contain many valid rectangles, and the algorithm must return the smallest area.

For example:

[[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]

There are two valid rectangles:

• Area 4
• Area 2

A naive implementation might stop after finding the first rectangle. This solution instead evaluates every valid rectangle and continuously updates the minimum area, guaranteeing the correct result.