Minimum Area Rectangle

🎯

Minimum Area Rectangle

mediumMATHAmazonGoogle

Imagine you have a set of points representing trees in a park, and you want to build the smallest rectangular fence that encloses four of them as corners. How do you find that rectangle with minimum area?

💡 This problem involves geometry and coordinate math, which can be tricky because it requires understanding how points relate spatially. Beginners often struggle to see how to efficiently check for rectangles among many points without checking every combination naively.

📋

Problem Statement

Given a set of points in the 2D plane, find the minimum area of any rectangle formed by four of these points with sides parallel to the x and y axes. If no such rectangle exists, return 0. Input: An array of points where each point is represented as [x, y]. Output: The minimum area of a rectangle formed by any four points, or 0 if none exists.

1 ≤ n ≤ 10^50 ≤ x, y ≤ 10^9All points are distinct

💡

Example

Input"[[1,1],[1,3],[3,1],[3,3],[2,2]]"

Output4

The rectangle formed by points (1,1), (1,3), (3,1), and (3,3) has area 4, which is the minimum.

• No rectangle possible → output 0
• All points on a single line → output 0
• Multiple rectangles → output minimum area among them
• Points with large coordinates → ensure no integer overflow

⚠️

Common Mistakes

Checking pairs with same x or y as diagonals

Incorrect rectangles counted or zero area rectangles

✅ Ensure diagonal points have different x and y coordinates

Not using a hash set for point existence checks

Code becomes too slow due to repeated linear searches

✅ Store points in a hash set for O(1) lookups

Calculating area incorrectly (e.g., mixing x and y coordinates)

Wrong area values leading to wrong minimum

✅ Calculate area as abs(x1 - x2) * abs(y1 - y2)

Returning minimum area without checking if any rectangle was found

Returns infinity or garbage value instead of 0

✅ Return 0 if minimum area remains infinity or max int

Using floating point midpoint instead of scaled integers

Precision errors cause missed matches

✅ Use sum of coordinates (scaled midpoint) as integer key

🧠

Brute Force (Check All Quadruples)

💡 This approach exists to build intuition by trying every possible combination of four points to check if they form a rectangle. It is too slow for large inputs but helps understand the problem deeply.

Intuition

Try every set of four points and check if they form a rectangle with sides parallel to axes. Calculate the area if they do, and track the minimum.

Algorithm

1. Enumerate all quadruples of points.
2. For each quadruple, check if they form a rectangle with sides parallel to axes.
3. If yes, compute the area and update the minimum area found.
4. Return the minimum area or 0 if none found.

💡 The challenge is to correctly identify rectangles and handle all quadruples, which is straightforward but computationally expensive.

</>

Code

from itertools import combinations

def minAreaRect(points):
    point_set = set(map(tuple, points))
    min_area = float('inf')
    for p1, p2, p3, p4 in combinations(points, 4):
        xs = {p1[0], p2[0], p3[0], p4[0]}
        ys = {p1[1], p2[1], p3[1], p4[1]}
        if len(xs) == 2 and len(ys) == 2:
            # Check all four corners exist
            corners = [(x, y) for x in xs for y in ys]
            if all(c in point_set for c in corners):
                area = abs(max(xs) - min(xs)) * abs(max(ys) - min(ys))
                if area < min_area:
                    min_area = area
    return 0 if min_area == float('inf') else min_area

# Driver code
points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
print(minAreaRect(points))

Line Notes

from itertools import combinationsImport combinations to generate all quadruples of points

point_set = set(map(tuple, points))Convert points to a set for O(1) membership checks

for p1, p2, p3, p4 in combinations(points, 4)Enumerate every group of 4 points to check rectangles

xs = {p1[0], p2[0], p3[0], p4[0]}Collect distinct x-coordinates of the quadruple

ys = {p1[1], p2[1], p3[1], p4[1]}Collect distinct y-coordinates of the quadruple

if len(xs) == 2 and len(ys) == 2A rectangle aligned with axes must have exactly 2 distinct x and y coordinates

corners = [(x, y) for x in xs for y in ys]Generate all four corners of the rectangle

if all(c in point_set for c in corners)Verify all four corners exist in the input points

area = abs(max(xs) - min(xs)) * abs(max(ys) - min(ys))Calculate area of the rectangle

return 0 if min_area == float('inf') else min_areaReturn 0 if no rectangle found

import java.util.*;

public class MinAreaRectBrute {
    private static Set<Integer> getDistinct(Set<Integer> set, int... vals) {
        for (int v : vals) set.add(v);
        return set;
    }

    public static int minAreaRect(int[][] points) {
        Set<String> pointSet = new HashSet<>();
        for (int[] p : points) {
            pointSet.add(p[0] + "," + p[1]);
        }
        int minArea = Integer.MAX_VALUE;
        int n = points.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    for (int l = k + 1; l < n; l++) {
                        int[] p1 = points[i], p2 = points[j], p3 = points[k], p4 = points[l];
                        Set<Integer> xs = new HashSet<>();
                        xs.add(p1[0]); xs.add(p2[0]); xs.add(p3[0]); xs.add(p4[0]);
                        Set<Integer> ys = new HashSet<>();
                        ys.add(p1[1]); ys.add(p2[1]); ys.add(p3[1]); ys.add(p4[1]);
                        if (xs.size() == 2 && ys.size() == 2) {
                            List<String> corners = new ArrayList<>();
                            for (int x : xs) {
                                for (int y : ys) {
                                    corners.add(x + "," + y);
                                }
                            }
                            boolean allExist = true;
                            for (String c : corners) {
                                if (!pointSet.contains(c)) {
                                    allExist = false;
                                    break;
                                }
                            }
                            if (allExist) {
                                int area = (Collections.max(xs) - Collections.min(xs)) * (Collections.max(ys) - Collections.min(ys));
                                if (area < minArea) minArea = area;
                            }
                        }
                    }
                }
            }
        }
        return minArea == Integer.MAX_VALUE ? 0 : minArea;
    }

    public static void main(String[] args) {
        int[][] points = {{1,1},{1,3},{3,1},{3,3},{2,2}};
        System.out.println(minAreaRect(points));
    }
}

Line Notes

Set<String> pointSet = new HashSet<>();Store points as strings for quick lookup

for (int i = 0; i < n; i++)Outer loop to pick first point

for (int j = i + 1; j < n; j++)Second point of quadruple

for (int k = j + 1; k < n; k++)Third point of quadruple

for (int l = k + 1; l < n; l++)Fourth point of quadruple

Set<Integer> xs = new HashSet<>(); xs.add(...)Collect distinct x-coordinates of quadruple

Set<Integer> ys = new HashSet<>(); ys.add(...)Collect distinct y-coordinates of quadruple

if (xs.size() == 2 && ys.size() == 2)Check if quadruple can form rectangle corners

for (int x : xs) { for (int y : ys) {Generate all four corners of rectangle

if (!pointSet.contains(c))Verify all corners exist in input

int area = (Collections.max(xs) - Collections.min(xs)) * (Collections.max(ys) - Collections.min(ys));Calculate rectangle area

return minArea == Integer.MAX_VALUE ? 0 : minArea;Return 0 if no rectangle found

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

string toStr(int x, int y) {
    return to_string(x) + "," + to_string(y);
}

int minAreaRect(vector<vector<int>>& points) {
    unordered_set<string> pointSet;
    for (auto& p : points) {
        pointSet.insert(toStr(p[0], p[1]));
    }
    int n = points.size();
    int minArea = INT_MAX;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                for (int l = k + 1; l < n; l++) {
                    vector<int> xs = {points[i][0], points[j][0], points[k][0], points[l][0]};
                    vector<int> ys = {points[i][1], points[j][1], points[k][1], points[l][1]};
                    sort(xs.begin(), xs.end());
                    xs.erase(unique(xs.begin(), xs.end()), xs.end());
                    sort(ys.begin(), ys.end());
                    ys.erase(unique(ys.begin(), ys.end()), ys.end());
                    if (xs.size() == 2 && ys.size() == 2) {
                        bool allExist = true;
                        for (int x : xs) {
                            for (int y : ys) {
                                if (pointSet.find(toStr(x, y)) == pointSet.end()) {
                                    allExist = false;
                                    break;
                                }
                            }
                            if (!allExist) break;
                        }
                        if (allExist) {
                            int area = (xs[1] - xs[0]) * (ys[1] - ys[0]);
                            if (area < minArea) minArea = area;
                        }
                    }
                }
            }
        }
    }
    return minArea == INT_MAX ? 0 : minArea;
}

int main() {
    vector<vector<int>> points = {{1,1},{1,3},{3,1},{3,3},{2,2}};
    cout << minAreaRect(points) << endl;
    return 0;
}

Line Notes

unordered_set<string> pointSet;Use hash set for O(1) point existence checks

for (int i = 0; i < n; i++)Outer loop picks first point

for (int j = i + 1; j < n; j++)Second point of quadruple

for (int k = j + 1; k < n; k++)Third point of quadruple

for (int l = k + 1; l < n; l++)Fourth point of quadruple

sort(xs.begin(), xs.end()); xs.erase(...)Remove duplicates to get distinct x-coordinates

sort(ys.begin(), ys.end()); ys.erase(...)Remove duplicates to get distinct y-coordinates

if (xs.size() == 2 && ys.size() == 2)Check if quadruple can form rectangle corners

for (int x : xs) { for (int y : ys) {Check all four corners exist

int area = (xs[1] - xs[0]) * (ys[1] - ys[0]);Calculate rectangle area

return minArea == INT_MAX ? 0 : minArea;Return 0 if no rectangle found

function minAreaRect(points) {
    const pointSet = new Set(points.map(p => p[0] + ',' + p[1]));
    let minArea = Infinity;
    const n = points.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            for (let k = j + 1; k < n; k++) {
                for (let l = k + 1; l < n; l++) {
                    const xs = new Set([points[i][0], points[j][0], points[k][0], points[l][0]]);
                    const ys = new Set([points[i][1], points[j][1], points[k][1], points[l][1]]);
                    if (xs.size === 2 && ys.size === 2) {
                        const xsArr = Array.from(xs);
                        const ysArr = Array.from(ys);
                        let allExist = true;
                        for (const x of xsArr) {
                            for (const y of ysArr) {
                                if (!pointSet.has(x + ',' + y)) {
                                    allExist = false;
                                    break;
                                }
                            }
                            if (!allExist) break;
                        }
                        if (allExist) {
                            const area = Math.abs(xsArr[0] - xsArr[1]) * Math.abs(ysArr[0] - ysArr[1]);
                            if (area < minArea) minArea = area;
                        }
                    }
                }
            }
        }
    }
    return minArea === Infinity ? 0 : minArea;
}

// Test
console.log(minAreaRect([[1,1],[1,3],[3,1],[3,3],[2,2]]));

Line Notes

const pointSet = new Set(points.map(p => p[0] + ',' + p[1]))Create a set for O(1) point lookup

for (let i = 0; i < n; i++)Outer loop picks first point

for (let j = i + 1; j < n; j++)Second point of quadruple

for (let k = j + 1; k < n; k++)Third point of quadruple

for (let l = k + 1; l < n; l++)Fourth point of quadruple

const xs = new Set([...])Collect distinct x-coordinates of quadruple

const ys = new Set([...])Collect distinct y-coordinates of quadruple

if (xs.size === 2 && ys.size === 2)Check if quadruple can form rectangle corners

for (const x of xsArr) { for (const y of ysArr) {Verify all four corners exist

const area = Math.abs(xsArr[0] - xsArr[1]) * Math.abs(ysArr[0] - ysArr[1])Calculate rectangle area

return minArea === Infinity ? 0 : minAreaReturn 0 if no rectangle found

⏱

Complexity

TimeO(n^4)

SpaceO(n)

We check all quadruples of points, which is O(n^4). Storing points in a set costs O(n) space.

💡 For n=20, this means about 160,000 operations, which is borderline but grows too fast for larger n.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and correctness before optimizing.

🧠

Better Approach Using Pairs of Points as Diagonals

💡 This approach improves efficiency by focusing on pairs of points that can be diagonals of rectangles, reducing the search space drastically.

Intuition

If two points form a diagonal of a rectangle, the other two corners must exist. We can group pairs by their midpoint and distance to find rectangles.

Algorithm

1. For each pair of points, compute the midpoint and squared distance.
2. Group pairs by (midpoint, distance) in a hash map.
3. For each group, check all pairs of pairs to find rectangles.
4. Calculate area for each rectangle and track the minimum.

💡 The key insight is that rectangles have equal diagonals with the same midpoint, so grouping pairs helps find rectangles efficiently.

</>

Code

def minAreaRect(points):
    from collections import defaultdict
    point_list = points
    pairs = defaultdict(list)
    n = len(point_list)
    for i in range(n):
        for j in range(i+1, n):
            x1, y1 = point_list[i]
            x2, y2 = point_list[j]
            mid_x = x1 + x2
            mid_y = y1 + y2
            dist = (x1 - x2)**2 + (y1 - y2)**2
            pairs[(mid_x, mid_y, dist)].append((i, j))
    min_area = float('inf')
    for key in pairs:
        pair_list = pairs[key]
        for i in range(len(pair_list)):
            for j in range(i+1, len(pair_list)):
                p1, p2 = pair_list[i]
                p3, p4 = pair_list[j]
                x1, y1 = point_list[p1]
                x2, y2 = point_list[p3]
                area = abs(x1 - x2) * abs(y1 - y2)
                if area != 0 and area < min_area:
                    min_area = area
    return 0 if min_area == float('inf') else min_area

# Driver code
points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
print(minAreaRect(points))

Line Notes

pairs = defaultdict(list)Group pairs by midpoint and distance to find potential diagonals

for i in range(n): for j in range(i+1, n):Enumerate all pairs of points

mid_x = x1 + x2; mid_y = y1 + y2Calculate midpoint (scaled by 2 to avoid floats)

dist = (x1 - x2)**2 + (y1 - y2)**2Calculate squared distance between points

pairs[(mid_x, mid_y, dist)].append((i, j))Store pairs sharing same midpoint and distance

for i in range(len(pair_list)): for j in range(i+1, len(pair_list))Check all pairs of pairs in group to find rectangles

area = abs(x1 - x2) * abs(y1 - y2)Calculate area of rectangle formed by these points

return 0 if min_area == float('inf') else min_areaReturn 0 if no rectangle found

import java.util.*;

public class MinAreaRectBetter {
    public static int minAreaRect(int[][] points) {
        Map<String, List<int[]>> map = new HashMap<>();
        int n = points.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int x1 = points[i][0], y1 = points[i][1];
                int x2 = points[j][0], y2 = points[j][1];
                int midX = x1 + x2;
                int midY = y1 + y2;
                int dist = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
                String key = midX + "," + midY + "," + dist;
                map.computeIfAbsent(key, k -> new ArrayList<>()).add(new int[]{i, j});
            }
        }
        int minArea = Integer.MAX_VALUE;
        for (List<int[]> pairs : map.values()) {
            int size = pairs.size();
            for (int i = 0; i < size; i++) {
                for (int j = i + 1; j < size; j++) {
                    int[] p1 = pairs.get(i);
                    int[] p2 = pairs.get(j);
                    int x1 = points[p1[0]][0], y1 = points[p1[0]][1];
                    int x2 = points[p2[0]][0], y2 = points[p2[0]][1];
                    int area = Math.abs(x1 - x2) * Math.abs(y1 - y2);
                    if (area != 0 && area < minArea) minArea = area;
                }
            }
        }
        return minArea == Integer.MAX_VALUE ? 0 : minArea;
    }

    public static void main(String[] args) {
        int[][] points = {{1,1},{1,3},{3,1},{3,3},{2,2}};
        System.out.println(minAreaRect(points));
    }
}

Line Notes

Map<String, List<int[]>> map = new HashMap<>();Map groups pairs by midpoint and distance to identify diagonals

for (int i = 0; i < n; i++)Enumerate first point of pair

for (int j = i + 1; j < n; j++)Enumerate second point of pair

String key = midX + "," + midY + "," + dist;Create unique key for midpoint and distance

map.computeIfAbsent(key, k -> new ArrayList<>()).add(new int[]{i, j});Store pair indices in map

for (List<int[]> pairs : map.values())Iterate over groups of pairs sharing diagonal

int area = Math.abs(x1 - x2) * Math.abs(y1 - y2);Calculate rectangle area from two pairs

return minArea == Integer.MAX_VALUE ? 0 : minArea;Return 0 if no rectangle found

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <cmath>
using namespace std;

string keyStr(int midX, int midY, int dist) {
    return to_string(midX) + "," + to_string(midY) + "," + to_string(dist);
}

int minAreaRect(vector<vector<int>>& points) {
    unordered_map<string, vector<pair<int,int>>> map;
    int n = points.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int x1 = points[i][0], y1 = points[i][1];
            int x2 = points[j][0], y2 = points[j][1];
            int midX = x1 + x2;
            int midY = y1 + y2;
            int dist = (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2);
            map[keyStr(midX, midY, dist)].push_back({i, j});
        }
    }
    int minArea = INT_MAX;
    for (auto& entry : map) {
        auto& pairs = entry.second;
        int size = pairs.size();
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                int x1 = points[pairs[i].first][0], y1 = points[pairs[i].first][1];
                int x2 = points[pairs[j].first][0], y2 = points[pairs[j].first][1];
                int area = abs(x1 - x2) * abs(y1 - y2);
                if (area != 0 && area < minArea) minArea = area;
            }
        }
    }
    return minArea == INT_MAX ? 0 : minArea;
}

int main() {
    vector<vector<int>> points = {{1,1},{1,3},{3,1},{3,3},{2,2}};
    cout << minAreaRect(points) << endl;
    return 0;
}

Line Notes

unordered_map<string, vector<pair<int,int>>> map;Map groups pairs by midpoint and distance to identify diagonals

for (int i = 0; i < n; i++)Enumerate first point of pair

for (int j = i + 1; j < n; j++)Enumerate second point of pair

map[keyStr(midX, midY, dist)].push_back({i, j});Store pair indices in map

for (auto& entry : map)Iterate over groups of pairs sharing diagonal

int area = abs(x1 - x2) * abs(y1 - y2);Calculate rectangle area from two pairs

return minArea == INT_MAX ? 0 : minArea;Return 0 if no rectangle found

function minAreaRect(points) {
    const map = new Map();
    const n = points.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const x1 = points[i][0], y1 = points[i][1];
            const x2 = points[j][0], y2 = points[j][1];
            const midX = x1 + x2;
            const midY = y1 + y2;
            const dist = (x1 - x2) ** 2 + (y1 - y2) ** 2;
            const key = midX + ',' + midY + ',' + dist;
            if (!map.has(key)) map.set(key, []);
            map.get(key).push([i, j]);
        }
    }
    let minArea = Infinity;
    for (const pairs of map.values()) {
        for (let i = 0; i < pairs.length; i++) {
            for (let j = i + 1; j < pairs.length; j++) {
                const [p1] = pairs[i];
                const [p3] = pairs[j];
                const x1 = points[p1][0], y1 = points[p1][1];
                const x2 = points[p3][0], y2 = points[p3][1];
                const area = Math.abs(x1 - x2) * Math.abs(y1 - y2);
                if (area !== 0 && area < minArea) minArea = area;
            }
        }
    }
    return minArea === Infinity ? 0 : minArea;
}

// Test
console.log(minAreaRect([[1,1],[1,3],[3,1],[3,3],[2,2]]));

Line Notes

const map = new Map();Map groups pairs by midpoint and distance to identify diagonals

for (let i = 0; i < n; i++)Enumerate first point of pair

for (let j = i + 1; j < n; j++)Enumerate second point of pair

const key = midX + ',' + midY + ',' + dist;Create unique key for midpoint and distance

map.get(key).push([i, j]);Store pair indices in map

for (const pairs of map.values())Iterate over groups of pairs sharing diagonal

const area = Math.abs(x1 - x2) * Math.abs(y1 - y2);Calculate rectangle area from two pairs

return minArea === Infinity ? 0 : minArea;Return 0 if no rectangle found

⏱

Complexity

TimeO(n^2 * m^2) worst case, typically O(n^2)

SpaceO(n^2)

We generate all pairs (O(n^2)) and group them by midpoint and distance. Checking pairs in groups can be costly if groups are large (m is max group size), worst case O(n^4), but typically groups are small, so average complexity is closer to O(n^2).

💡 For n=1000, this is about 1 million pairs, which is feasible with efficient implementation.

Interview Verdict: Accepted

This approach is efficient enough for large inputs and uses a clever geometric insight.

🧠

Optimal Approach Using Hash Set and Diagonal Pair Check

💡 This approach is optimal because it uses a hash set for constant time lookups and checks pairs as diagonals to find rectangles efficiently.

Intuition

For each pair of points that can be a diagonal, check if the other two corners exist by looking up in a hash set. This avoids grouping and reduces overhead.

Algorithm

1. Store all points in a hash set for O(1) lookup.
2. For each pair of points, if they can be diagonal corners (different x and y), check if the other two corners exist.
3. Calculate the area if rectangle found and update minimum area.
4. Return the minimum area or 0 if none found.

💡 The key is to quickly verify existence of the other two corners using the hash set, avoiding nested loops over pairs.

</>

Code

def minAreaRect(points):
    point_set = set(map(tuple, points))
    min_area = float('inf')
    n = len(points)
    for i in range(n):
        for j in range(i+1, n):
            x1, y1 = points[i]
            x2, y2 = points[j]
            if x1 != x2 and y1 != y2:
                if (x1, y2) in point_set and (x2, y1) in point_set:
                    area = abs(x1 - x2) * abs(y1 - y2)
                    if area < min_area:
                        min_area = area
    return 0 if min_area == float('inf') else min_area

# Driver code
points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
print(minAreaRect(points))

Line Notes

point_set = set(map(tuple, points))Store points in a set for O(1) existence checks

for i in range(n): for j in range(i+1, n):Enumerate all pairs of points

if x1 != x2 and y1 != y2Only pairs that can be diagonals of rectangles

if (x1, y2) in point_set and (x2, y1) in point_setCheck if other two corners exist

area = abs(x1 - x2) * abs(y1 - y2)Calculate rectangle area

if area < min_areaUpdate minimum area if smaller

return 0 if min_area == float('inf') else min_areaReturn 0 if no rectangle found

import java.util.*;

public class MinAreaRectOptimal {
    public static int minAreaRect(int[][] points) {
        Set<String> pointSet = new HashSet<>();
        for (int[] p : points) {
            pointSet.add(p[0] + "," + p[1]);
        }
        int minArea = Integer.MAX_VALUE;
        int n = points.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int x1 = points[i][0], y1 = points[i][1];
                int x2 = points[j][0], y2 = points[j][1];
                if (x1 != x2 && y1 != y2) {
                    if (pointSet.contains(x1 + "," + y2) && pointSet.contains(x2 + "," + y1)) {
                        int area = Math.abs(x1 - x2) * Math.abs(y1 - y2);
                        if (area < minArea) minArea = area;
                    }
                }
            }
        }
        return minArea == Integer.MAX_VALUE ? 0 : minArea;
    }

    public static void main(String[] args) {
        int[][] points = {{1,1},{1,3},{3,1},{3,3},{2,2}};
        System.out.println(minAreaRect(points));
    }
}

Line Notes

Set<String> pointSet = new HashSet<>();Store points as strings for quick lookup

for (int i = 0; i < n; i++)Outer loop picks first point

for (int j = i + 1; j < n; j++)Enumerate second point of pair

if (x1 != x2 && y1 != y2)Only consider pairs that can be diagonals

if (pointSet.contains(x1 + "," + y2) && pointSet.contains(x2 + "," + y1))Check existence of other two corners

int area = Math.abs(x1 - x2) * Math.abs(y1 - y2);Calculate rectangle area

if (area < minArea)Update minimum area if smaller

return minArea == Integer.MAX_VALUE ? 0 : minArea;Return 0 if no rectangle found

#include <iostream>
#include <vector>
#include <unordered_set>
#include <string>
#include <cmath>
using namespace std;

string toStr(int x, int y) {
    return to_string(x) + "," + to_string(y);
}

int minAreaRect(vector<vector<int>>& points) {
    unordered_set<string> pointSet;
    for (auto& p : points) {
        pointSet.insert(toStr(p[0], p[1]));
    }
    int n = points.size();
    int minArea = INT_MAX;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int x1 = points[i][0], y1 = points[i][1];
            int x2 = points[j][0], y2 = points[j][1];
            if (x1 != x2 && y1 != y2) {
                if (pointSet.find(toStr(x1, y2)) != pointSet.end() && pointSet.find(toStr(x2, y1)) != pointSet.end()) {
                    int area = abs(x1 - x2) * abs(y1 - y2);
                    if (area < minArea) minArea = area;
                }
            }
        }
    }
    return minArea == INT_MAX ? 0 : minArea;
}

int main() {
    vector<vector<int>> points = {{1,1},{1,3},{3,1},{3,3},{2,2}};
    cout << minAreaRect(points) << endl;
    return 0;
}

Line Notes

unordered_set<string> pointSet;Hash set for O(1) point existence checks

for (int i = 0; i < n; i++)Outer loop picks first point

for (int j = i + 1; j < n; j++)Enumerate second point of pair

if (x1 != x2 && y1 != y2)Only pairs that can be diagonals

if (pointSet.find(toStr(x1, y2)) != pointSet.end() && pointSet.find(toStr(x2, y1)) != pointSet.end())Check other two corners exist

int area = abs(x1 - x2) * abs(y1 - y2);Calculate rectangle area

if (area < minArea)Update minimum area if smaller

return minArea == INT_MAX ? 0 : minArea;Return 0 if no rectangle found

function minAreaRect(points) {
    const pointSet = new Set(points.map(p => p[0] + ',' + p[1]));
    let minArea = Infinity;
    const n = points.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const [x1, y1] = points[i];
            const [x2, y2] = points[j];
            if (x1 !== x2 && y1 !== y2) {
                if (pointSet.has(x1 + ',' + y2) && pointSet.has(x2 + ',' + y1)) {
                    const area = Math.abs(x1 - x2) * Math.abs(y1 - y2);
                    if (area < minArea) minArea = area;
                }
            }
        }
    }
    return minArea === Infinity ? 0 : minArea;
}

// Test
console.log(minAreaRect([[1,1],[1,3],[3,1],[3,3],[2,2]]));

Line Notes

const pointSet = new Set(points.map(p => p[0] + ',' + p[1]))Create set for O(1) point lookup

for (let i = 0; i < n; i++)Outer loop picks first point

for (let j = i + 1; j < n; j++)Enumerate second point of pair

if (x1 !== x2 && y1 !== y2)Only pairs that can be diagonals

if (pointSet.has(x1 + ',' + y2) && pointSet.has(x2 + ',' + y1))Check other two corners exist

const area = Math.abs(x1 - x2) * Math.abs(y1 - y2)Calculate rectangle area

if (area < minArea)Update minimum area if smaller

return minArea === Infinity ? 0 : minAreaReturn 0 if no rectangle found

⏱

Complexity

TimeO(n^2)

SpaceO(n)

We check all pairs (O(n^2)) and do O(1) lookups for other corners. Space is O(n) for the hash set storing all points.

💡 For n=10,000, this is about 50 million operations, which is feasible with efficient code.

Interview Verdict: Accepted

This is the best practical solution combining simplicity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 The optimal hash set diagonal check approach is what you should code in 95% of interviews due to its clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^4)	O(n)	No	N/A	Mention only - never code due to inefficiency
2. Diagonal Pair Grouping	O(n^2 * m^2) worst, typically O(n^2)	O(n^2)	No	N/A	Explain as intermediate optimization
3. Optimal Hash Set Diagonal Check	O(n^2)	O(n)	No	N/A	Code this approach in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, starting from brute force to optimal solutions. Practice explaining each approach clearly before coding.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Describe the brute force approach to show understanding.Step 3: Explain the diagonal pair grouping approach to improve efficiency.Step 4: Present the optimal hash set diagonal check solution.Step 5: Code the optimal solution and test with examples.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 2min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of geometry, hashing, and optimization from naive to efficient solutions.

Common Follow-ups

• What if points are not distinct? → Handle duplicates carefully or preprocess.
• Can you handle rectangles not aligned with axes? → Requires different approach using vector math.

💡 These follow-ups test your ability to generalize and handle edge cases beyond the base problem.

🔍

Pattern Recognition

When to Use

1) Given points in 2D plane, 2) Need to find rectangles or shapes, 3) Rectangles aligned with axes, 4) Need minimum or maximum area

Signature Phrases

'minimum area of any rectangle formed by points''sides parallel to the x and y axes'

NOT This Pattern When

Problems involving arbitrary rotated rectangles or polygons require different vector math approaches.

Similar Problems

Largest Rectangle in Histogram - also about finding max/min rectangle areaMaximal Rectangle - finding largest rectangle in a matrixRectangle Area - computing area covered by rectangles

Practice

1. Given the following Python code to find the nth ugly number, what is the output when calling nthUglyNumber(4)?

import heapq

def nthUglyNumber(n):
    heap = [1]
    seen = {1}
    ugly = 1
    for _ in range(n):
        ugly = heapq.heappop(heap)
        for factor in [2, 3, 5]:
            new_ugly = ugly * factor
            if new_ugly not in seen:
                seen.add(new_ugly)
                heapq.heappush(heap, new_ugly)
    return ugly

print(nthUglyNumber(4))

easy

A. 6

B. 5

C. 8

D. 4

Solution

1. Step 1: Trace heap pops and pushes for n=4

   Initial heap: [1]. Iteration 1 pops 1, pushes 2,3,5. Iteration 2 pops 2, pushes 4,6,10. Iteration 3 pops 3, pushes 6 (already seen), 9, 15. Iteration 4 pops 4, pushes 8,12,20.

2. Step 2: Identify the 4th popped ugly number

   The popped numbers in order are 1, 2, 3, 4. The 4th ugly number is 4, so nthUglyNumber(4) returns 4.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   4 is the 4th ugly number generated by the heap [OK]

Hint: Heap pops nth ugly number in ascending order [OK]

Common Mistakes:

• Confusing the iteration count with the returned value
• Forgetting duplicates are skipped
• Miscounting the order of popped elements

2. Consider the following buggy code for finding the nth ugly number. Which line contains the subtle bug that causes incorrect results for some inputs?

import heapq

def nthUglyNumber(n):
    heap = [1]
    seen = set()
    ugly = 1
    for _ in range(n):
        ugly = heapq.heappop(heap)
        for factor in [2, 3, 5]:
            new_ugly = ugly * factor
            if new_ugly not in seen:
                seen.add(new_ugly)
                heapq.heappush(heap, new_ugly)
    return ugly

medium

A. Line 3: Initializing seen as an empty set instead of containing 1

B. Line 6: Popping from heap before checking if heap is empty

C. Line 9: Multiplying ugly by factor without checking for overflow

D. Line 11: Adding new_ugly to seen before pushing to heap

Solution

1. Step 1: Check initialization of seen set

   The seen set is empty initially, but 1 is already in the heap. This causes duplicates because 1 is not marked as seen.

2. Step 2: Understand impact of missing 1 in seen

   Without 1 in seen, the algorithm may push 1 multiple times, causing duplicates and incorrect nth ugly number.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Adding 1 to seen fixes duplicates and ensures correctness [OK]

Hint: Always mark initial heap elements as seen to avoid duplicates [OK]

Common Mistakes:

• Forgetting to add initial element to seen set
• Assuming heap uniqueness without seen tracking
• Ignoring edge cases with initial values

3. Suppose the clock can show times with fractional minutes (e.g., 3:30.5). Which modification to the precomputation approach is necessary to handle queries with fractional minutes correctly?

hard

A. Increase precomputed table size to include fractional minute indices (e.g., 60 * 10 for tenths of minutes).

B. Precompute only hour angles and calculate minute angles on the fly for fractional minutes.

C. Round fractional minutes down to nearest integer and use existing precomputed table.

D. Use the brute force direct calculation formula at query time instead of precomputation.

Solution

1. Step 1: Understand fractional minute impact

   Precomputing all fractional minute values is infeasible due to infinite possibilities.

2. Step 2: Evaluate options

   Increasing table size exponentially is impractical; rounding loses precision; precomputing only hour angles is insufficient because minute angle varies continuously.

3. Step 3: Use direct calculation

   Calculating angles on the fly with the formula handles fractional minutes accurately and efficiently.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Direct formula supports fractional inputs without huge memory [OK]

Hint: Precompute only works for discrete inputs; fractional requires formula [OK]

Common Mistakes:

• Trying to precompute infinite fractional values
• Rounding fractional minutes losing accuracy

4. Suppose you want to extend the happy number check to negative integers by applying the same digit square sum process on their absolute values. Which modification to the algorithm is necessary to correctly handle negative inputs?

hard

A. Add a check to convert negative input to positive before processing digits.

B. Modify digit extraction to handle negative digits directly without conversion.

C. Use recursion instead of iteration to handle negative inputs.

D. No modification needed; the existing algorithm works for negative numbers.

Solution

1. Step 1: Understand digit extraction for negatives

   Digit extraction using modulo and division assumes non-negative numbers; negative digits do not exist.

2. Step 2: Convert negative input to positive

   Taking absolute value ensures digit extraction works correctly and the sum of squares is computed properly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Absolute value conversion fixes digit extraction for negatives [OK]

Hint: Digit extraction requires non-negative numbers [OK]

Common Mistakes:

• Trying to extract digits from negative directly
• Assuming recursion helps
• Ignoring sign issues

5. Suppose you want to find the nth ugly number but now the problem allows reusing the same ugly number multiple times in the heap without tracking duplicates. Which modification to the algorithm is necessary to maintain correctness and efficiency?

hard

A. Use three pointers to generate multiples in sorted order instead of a heap to avoid duplicates without tracking.

B. Remove the seen set and rely on the heap to naturally order numbers, accepting duplicates.

C. Keep the seen set but reset it periodically to allow reuse of numbers after some iterations.

D. Use a hash map to count occurrences of each ugly number and only push when count is below a threshold.

Solution

1. Step 1: Understand the impact of removing duplicate tracking

   Without a seen set, duplicates flood the heap, causing inefficiency and incorrect nth number.

2. Step 2: Identify alternative approach to avoid duplicates

   The three-pointer method generates ugly numbers in sorted order without duplicates by merging multiples of 2, 3, and 5.

3. Step 3: Conclude the necessary modification

   Switching to the three-pointer approach avoids duplicates inherently, maintaining correctness and efficiency.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Three-pointer approach is standard for duplicate-free generation without extra sets [OK]

Hint: Three-pointer method avoids duplicates without extra memory [OK]

Common Mistakes:

• Assuming heap alone can handle duplicates efficiently
• Trying to reset or partially track duplicates incorrectly
• Using counters without clear threshold logic