Minimum Area Rectangle - Solution & Explanation

Problem Overview: You receive a list of 2D points on a grid. Four of those points can form an axis-aligned rectangle if they share two distinct x-coordinates and two distinct y-coordinates. The goal is to compute the smallest possible rectangle area formed by any four points. If no rectangle exists, return 0.

Approach 1: Using Dynamic Programming (O(n^2) time, O(n^2) space)

Group points by their x coordinate so each column contains the y values that appear at that x-position. Sort the y values within each column. For every pair of (y1, y2) in the same column, treat it as a potential vertical edge of a rectangle. Maintain a DP structure dp[y1][y2] that stores the last x coordinate where this pair appeared. When the same pair appears in a new column, you have two vertical edges. The rectangle area becomes (x - dp[y1][y2]) * (y2 - y1). Update the minimum area and refresh the stored column.

This works because a rectangle is uniquely determined by two vertical edges with identical y pairs. The DP table remembers where each vertical edge pair previously occurred, allowing constant-time area calculation when the pair reappears. The approach relies heavily on fast lookups using a structure similar to a hash table while iterating through sorted columns of points.

Approach 2: Optimizing Space using Two Variables (O(n^2) time, O(n) space)

The full DP table can grow large if many unique y values exist. Instead of storing a dense 2D matrix for dp[y1][y2], track pairs using a compact key such as (y1, y2) in a hash map. For each column, iterate through all combinations of two y values. The map stores the last column where that pair appeared. When encountered again, compute the area using the previous column and update the minimum rectangle.

This optimization removes the need for a large DP matrix while preserving the same logic. Each pair is processed using constant-time hash lookups. The algorithm still scans all vertical pairs in each column, so the time complexity remains O(n^2), but memory drops significantly because only observed pairs are stored. The approach fits well for sparse coordinate distributions often seen in geometry problems.

Recommended for interviews: Interviewers typically expect the hash-based pair tracking approach (Approach 2). A brute-force rectangle check over all point quadruples shows basic understanding but is too slow. Demonstrating the vertical edge insight and storing (y1, y2) pairs in a array/hash structure shows strong problem-solving and familiarity with geometric pattern recognition.