Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumsweep-line

Minimum Area Rectangle

Problem (restated)

Given distinct points on the plane, return the minimum area of an axis-aligned rectangle they determine, or 0 if none exists.

Intuition

An axis-aligned rectangle is two distinct x-coordinates and two distinct y-coordinates that all four corners exist. Sweep vertical lines left to right: for each pair of x’s, the shared y’s are candidate horizontal edges. For a fixed width, the smallest height is the closest pair of shared y’s.

Approaches

Sweep vertical lines

Unverified

Time O(n²)Space O(n)

Idea. Map x → set of y. Sort the x’s. For each pair x1 < x2, intersect y-sets, sort the common y’s, and try consecutive pairs: area dx * dy. Keep the min; 0 if none.

Walkthrough. (1,1),(1,3),(3,1),(3,3) share y=3 on x=1 and x=3 → area 4. Extra points on those lines can only shrink dy.

Trade-offs. Consecutive shared y’s are enough: width is fixed, so min height is the closest pair. Pairing every two points as a diagonal is the same complexity and messier. No rectangle → 0, not infinity.

Solution

export function minAreaRect(points: number[][]): number {
  const byX = new Map<number, Set<number>>();
  for (const p of points) {
    const x = p[0]!, y = p[1]!;
    if (!byX.has(x)) byX.set(x, new Set());
    byX.get(x)!.add(y);
  }
  const xs = [...byX.keys()].sort((a, b) => a - b);
  let ans = Infinity;
  for (let i = 0; i < xs.length; i++) {
    const ys1 = byX.get(xs[i]!)!;
    for (let j = i + 1; j < xs.length; j++) {
      const common: number[] = [];
      for (const y of byX.get(xs[j]!)!) if (ys1.has(y)) common.push(y);
      if (common.length < 2) continue;
      common.sort((a, b) => a - b);
      const dx = xs[j]! - xs[i]!;
      for (let k = 1; k < common.length; k++) {
        const area = dx * (common[k]! - common[k - 1]!);
        if (area < ans) ans = area;
      }
    }
  }
  return ans === Infinity ? 0 : ans;
}

export function minAreaRect(points: number[][]): number {
  const byX = new Map<number, Set<number>>();
  for (const p of points) {
    const x = p[0]!, y = p[1]!;
    if (!byX.has(x)) byX.set(x, new Set());
    byX.get(x)!.add(y);
  }
  const xs = [...byX.keys()].sort((a, b) => a - b);
  let ans = Infinity;
  for (let i = 0; i < xs.length; i++) {
    const ys1 = byX.get(xs[i]!)!;
    for (let j = i + 1; j < xs.length; j++) {
      const common: number[] = [];
      for (const y of byX.get(xs[j]!)!) if (ys1.has(y)) common.push(y);
      if (common.length < 2) continue;
      common.sort((a, b) => a - b);
      const dx = xs[j]! - xs[i]!;
      for (let k = 1; k < common.length; k++) {
        const area = dx * (common[k]! - common[k - 1]!);
        if (area < ans) ans = area;
      }
    }
  }
  return ans === Infinity ? 0 : ans;
}

Template connection

Sweep vertical lines, then a 1D overlap (shared y’s) at each pair of event x’s. Same “sort by x, look at the active y-set” skeleton as a rectangle sweep, without enter/exit because points have no width.

Reflection

Points that share x form a vertical line. Between two x-coordinates, look at the shared y-values. Each consecutive shared pair is a rectangle of area dx * dy.
No shared y means no rectangle, so the answer is 0. Keep the smallest positive area.
A diagonal is not a side. Three points are not enough. The same point twice does not create area.