Minimum Area Rectangle

LeetCode 976 | Difficulty: Medium

Medium

Problem Description

You are given an array of points in the X-Y plane points where points[i] = [x~i~, y~i~].

Return the minimum area of a rectangle formed from these points, with sides parallel to the X and Y axes. If there is not any such rectangle, return 0.

Example 1:

Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4

Example 2:

Input: points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Output: 2

Constraints:

- `1 <= points.length <= 500`

- `points[i].length == 2`

- `0 <= x~i~, y~i~ <= 4 * 10^4`

- All the given points are **unique**.

Topics: Array, Hash Table, Math, Geometry, Sorting

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 477 ms)

Metric	Value
Runtime	477 ms
Memory	39.2 MB
Date	2022-01-20

Solution

public class Solution {
    public int MinAreaRect(int[][] points) {
            int minArea = Int32.MaxValue;
    var coOrds = new Dictionary<int, List<int>>();
    foreach (var point in points)
    {
        if (!coOrds.ContainsKey(point[0]))
        {
            coOrds[point[0]] = new List<int>();
            coOrds[point[0]].Add(point[1]);
        }
        else
        {
            coOrds[point[0]].Add(point[1]);
        }
    }

    for (int i = 0; i < points.Length; i++)
    {
        for (int j = 0; j < i; j++)
        {
            int x1 = points[i][0];
            int y1 = points[i][1];
            int x2 = points[j][0];
            int y2 = points[j][1];

            if (x1 == x2 || y1 == y2)
                continue;


if (coOrds[x1].Contains(y2) && coOrds[x2].Contains(y1))
                {
                    minArea = Math.Min(minArea, Math.Abs((x1 - x2) * (y1 - y2)));
                }

        }
    }
    return minArea != Int32.MaxValue ? minArea : 0;
    }
}

📜 2 more C# submission(s)

Submission (2021-11-24) — 519 ms, 38.6 MB

public class Solution {
    public int MinAreaRect(int[][] points) {
            int minArea = Int32.MaxValue;
    var coOrds = new Dictionary<int, List<int>>();
    foreach (var point in points)
    {
        if (!coOrds.ContainsKey(point[0]))
        {
            coOrds[point[0]] = new List<int>();
            coOrds[point[0]].Add(point[1]);
        }
        else
        {
            coOrds[point[0]].Add(point[1]);
        }
    }

    for (int i = 0; i < points.Length; i++)
    {
        for (int j = 0; j < i; j++)
        {
            int x1 = points[i][0];
            int y1 = points[i][1];
            int x2 = points[j][0];
            int y2 = points[j][1];

            if (x1 == x2 || y1 == y2)
                continue;


            if (coOrds.ContainsKey(x1) && coOrds.ContainsKey(x2))
            {
                if (coOrds[x1].Contains(y2) && coOrds[x2].Contains(y1))
                {
                    minArea = Math.Min(minArea, Math.Abs((x1 - x2) * (y1 - y2)));
                }
            }
        }
    }
    return minArea != Int32.MaxValue ? minArea : 0;
    }
}

Submission (2021-11-24) — 548 ms, 41.4 MB

public class Solution {
    public int MinAreaRect(int[][] points) {
            int minArea = Int32.MaxValue;
    var coOrds = new Dictionary<int, List<int>> ();
    foreach (var point in points)
    {
        if (!coOrds.ContainsKey(point[0]))
        {
            coOrds[point[0]] = new List<int>();
            coOrds[point[0]].Add(point[1]);
        }
        else
        {
            coOrds[point[0]].Add(point[1]);
        }
    }
    
    foreach (var p1 in points)
    {
        foreach (var p2 in points)
        {
            int x1 = p1[0];
            int y1 = p1[1];
            int x2 = p2[0];
            int y2 = p2[1];

            if(x1 == x2 || y1 == y2)
            continue;
            

            if (coOrds.ContainsKey(x1) && coOrds.ContainsKey(x2))
            {
                if (coOrds[x1].Contains(y2) && coOrds[x2].Contains(y1))
                {
                    minArea = Math.Min(minArea, Math.Abs((x1 - x2) * (y1 - y2)));
                }
            }           
        }
        
        
    }
        return minArea != Int32.MaxValue ? minArea : 0;
    }
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Hash map gives O(1) lookup — think about what to use as key vs value.