Minimum Area Rectangle — Medium Problem & Solution

Problem statement

Given points on a plane, find the minimum area of a rectangle whose four corners are all among the given points and whose sides are parallel to the axes.

Return 0 if no such rectangle exists.

Example 1

Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4
Explanation: The four corner points form a 2 by 2 square.

Example 2

Input: points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Output: 2
Explanation: The columns at x = 3 and x = 4 give a 1 by 2 rectangle.

Example 3

Input: points = [[0,0],[1,1]]
Output: 0

Constraints

• 1 <= points.length <= 500
• points[i].length == 2
• 0 <= x, y <= 40000
• All points are distinct.

How to solve Minimum Area Rectangle

Pick two points as a diagonal. Their x and y values determine the remaining two corners exactly, so a set membership test decides whether the rectangle exists.

Approach

1. Insert every point into a set keyed on its coordinates.
2. For each ordered pair (i, j) with x1 < x2 and y1 < y2 — which fixes the diagonal's orientation and avoids double counting — check whether (x1, y2) and (x2, y1) are both present.
3. Track the smallest (x2 - x1) * (y2 - y1) found; return 0 if none.

Why it works

Sides parallel to the axes mean a rectangle's corner set is exactly {x1, x2} × {y1, y2}, so any two opposite corners determine the whole shape. Requiring x1 < x2 and y1 < y2 names each rectangle by its bottom-left and top-right corner once.

Complexity

• Time — O(n²)
• Space — O(n)

Pitfalls

• Allowing x1 == x2 or y1 == y2 degenerates the rectangle to a line with zero area.
• Encoding the point key as x * 40001 + y is fine, but a plain concatenation without a separator collides.
• 0 is the sentinel for 'no rectangle', so best cannot simply start at zero and use min — guard the first assignment.

Reference solution

Python

from typing import List

def minAreaRect(points: List[List[int]]) -> int:
    have = set((x, y) for x, y in points)
    best = 0
    for x1, y1 in points:
        for x2, y2 in points:
            if x1 >= x2 or y1 >= y2:
                continue
            if (x1, y2) in have and (x2, y1) in have:
                area = (x2 - x1) * (y2 - y1)
                if best == 0 or area < best:
                    best = area
    return best

JavaScript

var minAreaRect = function(points) {
    var have = {};
    for (var t = 0; t < points.length; t++) have[points[t][0] + ":" + points[t][1]] = true;
    var best = 0;
    for (var i = 0; i < points.length; i++) {
        for (var j = 0; j < points.length; j++) {
            var x1 = points[i][0], y1 = points[i][1];
            var x2 = points[j][0], y2 = points[j][1];
            if (x1 >= x2 || y1 >= y2) continue;
            if (have[x1 + ":" + y2] !== true || have[x2 + ":" + y1] !== true) continue;
            var area = (x2 - x1) * (y2 - y1);
            if (best === 0 || area < best) best = area;
        }
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Count Number of Texts Medium
• Construct String With Repeat Limit Medium
• Minimum Number of Steps to Make Two Strings Anagram II Medium
• Count Vowel Substrings of a String Medium
• Minimum Length of String After Operations Medium
• Sum of Digit Differences of All Pairs Medium