Minimum Area Rectangle

class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        map<int, vector<int>> cols;
        for (auto& p : points) cols[p[0]].push_back(p[1]);
        for (auto& [_, ys] : cols) sort(ys.begin(), ys.end());
        int ans = INT_MAX;
        vector<pair<int, vector<int>*>> arr;
        for (auto& [x, ys] : cols) arr.push_back({x, &ys});
        for (int i = 0; i < (int)arr.size(); ++i)
            for (int j = i + 1; j < (int)arr.size(); ++j) {
                auto& A = *arr[i].second;
                auto& B = *arr[j].second;
                int dx = arr[j].first - arr[i].first;
                int a = 0, b = 0, prev = -1;
                while (a < (int)A.size() && b < (int)B.size()) {
                    if (A[a] == B[b]) {
                        if (prev != -1) ans = min(ans, dx * (A[a] - prev));
                        prev = A[a];
                        ++a; ++b;
                    } else if (A[a] < B[b]) ++a;
                    else ++b;
                }
            }
        return ans == INT_MAX ? 0 : ans;
    }
};

func minAreaRect(points [][]int) int {
    cols := map[int][]int{}
    for _, p := range points {
        cols[p[0]] = append(cols[p[0]], p[1])
    }
    type colEntry struct {
        x  int
        ys []int
    }
    arr := make([]colEntry, 0, len(cols))
    for x, ys := range cols {
        sort.Ints(ys)
        arr = append(arr, colEntry{x, ys})
    }
    sort.Slice(arr, func(i, j int) bool { return arr[i].x < arr[j].x })
    ans := math.MaxInt32
    for i := 0; i < len(arr); i++ {
        for j := i + 1; j < len(arr); j++ {
            A, B := arr[i].ys, arr[j].ys
            dx := arr[j].x - arr[i].x
            a, b, prev := 0, 0, -1
            for a < len(A) && b < len(B) {
                if A[a] == B[b] {
                    if prev != -1 {
                        if v := dx * (A[a] - prev); v < ans {
                            ans = v
                        }
                    }
                    prev = A[a]
                    a++
                    b++
                } else if A[a] < B[b] {
                    a++
                } else {
                    b++
                }
            }
        }
    }
    if ans == math.MaxInt32 {
        return 0
    }
    return ans
}

from typing import List
from collections import defaultdict

class Solution:
    def minAreaRect(self, points: List[List[int]]) -> int:
        cols = defaultdict(list)
        for x, y in points:
            cols[x].append(y)
        for x in cols:
            cols[x].sort()
        arr = sorted(cols.items())
        ans = float('inf')
        for i in range(len(arr)):
            for j in range(i + 1, len(arr)):
                A, B = arr[i][1], arr[j][1]
                dx = arr[j][0] - arr[i][0]
                a, b, prev = 0, 0, -1
                while a < len(A) and b < len(B):
                    if A[a] == B[b]:
                        if prev != -1:
                            ans = min(ans, dx * (A[a] - prev))
                        prev = A[a]
                        a += 1
                        b += 1
                    elif A[a] < B[b]:
                        a += 1
                    else:
                        b += 1
        return 0 if ans == float('inf') else ans

function minAreaRect(points) {
    const cols = new Map();
    for (const [x, y] of points) {
        if (!cols.has(x)) cols.set(x, []);
        cols.get(x).push(y);
    }
    const arr = [];
    for (const [x, ys] of cols) {
        ys.sort((a, b) => a - b);
        arr.push([x, ys]);
    }
    arr.sort((a, b) => a[0] - b[0]);
    let ans = Infinity;
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            const A = arr[i][1], B = arr[j][1];
            const dx = arr[j][0] - arr[i][0];
            let a = 0, b = 0, prev = -1;
            while (a < A.length && b < B.length) {
                if (A[a] === B[b]) {
                    if (prev !== -1) ans = Math.min(ans, dx * (A[a] - prev));
                    prev = A[a];
                    a++;
                    b++;
                } else if (A[a] < B[b]) {
                    a++;
                } else {
                    b++;
                }
            }
        }
    }
    return ans === Infinity ? 0 : ans;
}

class Solution {
    public int minAreaRect(int[][] points) {
        Map<Integer, List<Integer>> cols = new TreeMap<>();
        for (int[] p : points) {
            cols.computeIfAbsent(p[0], k -> new ArrayList<>()).add(p[1]);
        }
        List<int[]> arr = new ArrayList<>();
        List<List<Integer>> ys = new ArrayList<>();
        for (Map.Entry<Integer, List<Integer>> e : cols.entrySet()) {
            Collections.sort(e.getValue());
            arr.add(new int[]{e.getKey(), arr.size()});
            ys.add(e.getValue());
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < arr.size(); i++) {
            for (int j = i + 1; j < arr.size(); j++) {
                List<Integer> A = ys.get(i), B = ys.get(j);
                int dx = arr.get(j)[0] - arr.get(i)[0];
                int a = 0, b = 0, prev = -1;
                while (a < A.size() && b < B.size()) {
                    int va = A.get(a), vb = B.get(b);
                    if (va == vb) {
                        if (prev != -1) ans = Math.min(ans, dx * (va - prev));
                        prev = va;
                        a++;
                        b++;
                    } else if (va < vb) {
                        a++;
                    } else {
                        b++;
                    }
                }
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

function minAreaRect(points: number[][]): number {
    const cols: Map<number, number[]> = new Map();
    for (const [x, y] of points) {
        if (!cols.has(x)) cols.set(x, []);
        (cols.get(x) as number[]).push(y);
    }
    const arr: [number, number[]][] = [];
    for (const [x, ys] of cols) {
        ys.sort((a, b) => a - b);
        arr.push([x, ys]);
    }
    arr.sort((a, b) => a[0] - b[0]);
    let ans = Infinity;
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            const A = arr[i][1], B = arr[j][1];
            const dx = arr[j][0] - arr[i][0];
            let a = 0, b = 0, prev = -1;
            while (a < A.length && b < B.length) {
                if (A[a] === B[b]) {
                    if (prev !== -1) ans = Math.min(ans, dx * (A[a] - prev));
                    prev = A[a];
                    a++;
                    b++;
                } else if (A[a] < B[b]) {
                    a++;
                } else {
                    b++;
                }
            }
        }
    }
    return ans === Infinity ? 0 : ans;
}