Maximum Area Rectangle With Point Constraints I

class Solution {
public:
    long long largestRectangleI(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());
        vector<pair<int, vector<int>*>> arr;
        for (auto& [x, ys] : cols) arr.push_back({x, &ys});
        long long best = -1;
        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;
                vector<int> shared;
                int a = 0, b = 0;
                while (a < (int)A.size() && b < (int)B.size()) {
                    if (A[a] == B[b]) { shared.push_back(A[a]); ++a; ++b; }
                    else if (A[a] < B[b]) ++a; else ++b;
                }
                for (int p = 0; p + 1 < (int)shared.size(); ++p) {
                    int y1 = shared[p], y2 = shared[p + 1];
                    bool ok = true;
                    for (int m = i + 1; m < j && ok; ++m) {
                        auto& Y = *arr[m].second;
                        auto it = lower_bound(Y.begin(), Y.end(), y1);
                        if (it != Y.end() && *it <= y2) ok = false;
                    }
                    auto check = [&](vector<int>& Y, int y1, int y2) {
                        auto it = upper_bound(Y.begin(), Y.end(), y1);
                        return it != Y.end() && *it < y2;
                    };
                    if (ok && !check(A, y1, y2) && !check(B, y1, y2)) {
                        long long dx = arr[j].first - arr[i].first;
                        best = max(best, dx * (long long)(y2 - y1));
                    }
                }
            }
        return best;
    }
};

import "sort"

func largestRectangleI(points [][]int) int64 {
    cols := map[int][]int{}
    for _, p := range points {
        cols[p[0]] = append(cols[p[0]], p[1])
    }
    xs := make([]int, 0, len(cols))
    for x, ys := range cols {
        sort.Ints(ys)
        xs = append(xs, x)
    }
    sort.Ints(xs)
    arr := make([][]int, len(xs))
    for i, x := range xs {
        arr[i] = cols[x]
    }
    var best int64 = -1
    check := func(Y []int, y1, y2 int) bool {
        it := sort.SearchInts(Y, y1+1)
        return it != len(Y) && Y[it] < y2
    }
    for i := 0; i < len(arr); i++ {
        for j := i + 1; j < len(arr); j++ {
            A, B := arr[i], arr[j]
            var shared []int
            a, b := 0, 0
            for a < len(A) && b < len(B) {
                if A[a] == B[b] {
                    shared = append(shared, A[a])
                    a++
                    b++
                } else if A[a] < B[b] {
                    a++
                } else {
                    b++
                }
            }
            for p := 0; p+1 < len(shared); p++ {
                y1, y2 := shared[p], shared[p+1]
                ok := true
                for m := i + 1; m < j && ok; m++ {
                    Y := arr[m]
                    it := sort.SearchInts(Y, y1)
                    if it != len(Y) && Y[it] <= y2 {
                        ok = false
                    }
                }
                if ok && !check(A, y1, y2) && !check(B, y1, y2) {
                    dx := int64(xs[j] - xs[i])
                    area := dx * int64(y2-y1)
                    if area > best {
                        best = area
                    }
                }
            }
        }
    }
    return best
}

import bisect
from collections import defaultdict
from typing import List

class Solution:
    def largestRectangleI(self, points: List[List[int]]) -> int:
        cols: dict = defaultdict(list)
        for x, y in points:
            cols[x].append(y)
        xs = sorted(cols.keys())
        for x in xs:
            cols[x].sort()
        arr = [cols[x] for x in xs]

        def check(Y: List[int], y1: int, y2: int) -> bool:
            it = bisect.bisect_right(Y, y1)
            return it != len(Y) and Y[it] < y2

        best = -1
        for i in range(len(arr)):
            for j in range(i + 1, len(arr)):
                A, B = arr[i], arr[j]
                shared: List[int] = []
                a = b = 0
                while a < len(A) and b < len(B):
                    if A[a] == B[b]:
                        shared.append(A[a])
                        a += 1
                        b += 1
                    elif A[a] < B[b]:
                        a += 1
                    else:
                        b += 1
                for p in range(len(shared) - 1):
                    y1, y2 = shared[p], shared[p + 1]
                    ok = True
                    for m in range(i + 1, j):
                        Y = arr[m]
                        it = bisect.bisect_left(Y, y1)
                        if it != len(Y) and Y[it] <= y2:
                            ok = False
                            break
                    if ok and not check(A, y1, y2) and not check(B, y1, y2):
                        dx = xs[j] - xs[i]
                        area = dx * (y2 - y1)
                        if area > best:
                            best = area
        return best

function largestRectangleI(points) {
    const cols = new Map();
    for (const [x, y] of points) {
        if (!cols.has(x)) cols.set(x, []);
        cols.get(x).push(y);
    }
    const xs = [...cols.keys()].sort((a, b) => a - b);
    for (const x of xs) cols.get(x).sort((a, b) => a - b);
    const arr = xs.map(x => cols.get(x));

    // first index where Y[i] > v
    const upperBound = (Y, v) => {
        let lo = 0, hi = Y.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (Y[mid] <= v) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    };
    // first index where Y[i] >= v
    const lowerBound = (Y, v) => {
        let lo = 0, hi = Y.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (Y[mid] < v) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    };
    const check = (Y, y1, y2) => {
        const it = upperBound(Y, y1);
        return it !== Y.length && Y[it] < y2;
    };

    let best = -1;
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            const A = arr[i], B = arr[j];
            const shared = [];
            let a = 0, b = 0;
            while (a < A.length && b < B.length) {
                if (A[a] === B[b]) { shared.push(A[a]); a++; b++; }
                else if (A[a] < B[b]) a++;
                else b++;
            }
            for (let p = 0; p + 1 < shared.length; p++) {
                const y1 = shared[p], y2 = shared[p + 1];
                let ok = true;
                for (let m = i + 1; m < j && ok; m++) {
                    const Y = arr[m];
                    const it = lowerBound(Y, y1);
                    if (it !== Y.length && Y[it] <= y2) ok = false;
                }
                if (ok && !check(A, y1, y2) && !check(B, y1, y2)) {
                    const dx = xs[j] - xs[i];
                    const area = dx * (y2 - y1);
                    if (area > best) best = area;
                }
            }
        }
    }
    return best;
}

class Solution {
    public long largestRectangleI(int[][] points) {
        TreeMap<Integer, List<Integer>> cols = new TreeMap<>();
        for (int[] p : points) {
            cols.computeIfAbsent(p[0], k -> new ArrayList<>()).add(p[1]);
        }
        List<Integer> xs = new ArrayList<>(cols.keySet());
        List<int[]> arr = new ArrayList<>();
        for (int x : xs) {
            List<Integer> ys = cols.get(x);
            Collections.sort(ys);
            int[] a = new int[ys.size()];
            for (int i = 0; i < ys.size(); i++) a[i] = ys.get(i);
            arr.add(a);
        }
        long best = -1;
        for (int i = 0; i < arr.size(); i++) {
            for (int j = i + 1; j < arr.size(); j++) {
                int[] A = arr.get(i), B = arr.get(j);
                List<Integer> shared = new ArrayList<>();
                int a = 0, b = 0;
                while (a < A.length && b < B.length) {
                    if (A[a] == B[b]) {
                        shared.add(A[a]);
                        a++;
                        b++;
                    } else if (A[a] < B[b]) a++;
                    else b++;
                }
                for (int p = 0; p + 1 < shared.size(); p++) {
                    int y1 = shared.get(p), y2 = shared.get(p + 1);
                    boolean ok = true;
                    for (int m = i + 1; m < j && ok; m++) {
                        int[] Y = arr.get(m);
                        int it = lowerBound(Y, y1);
                        if (it != Y.length && Y[it] <= y2) ok = false;
                    }
                    if (ok && !check(A, y1, y2) && !check(B, y1, y2)) {
                        long dx = (long)(xs.get(j) - xs.get(i));
                        long area = dx * (y2 - y1);
                        if (area > best) best = area;
                    }
                }
            }
        }
        return best;
    }

    private boolean check(int[] Y, int y1, int y2) {
        int it = upperBound(Y, y1);
        return it != Y.length && Y[it] < y2;
    }

    private int lowerBound(int[] Y, int v) {
        int lo = 0, hi = Y.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (Y[mid] < v) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    private int upperBound(int[] Y, int v) {
        int lo = 0, hi = Y.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (Y[mid] <= v) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}

function largestRectangleI(points: number[][]): number {
    const cols = new Map<number, number[]>();
    for (const [x, y] of points) {
        if (!cols.has(x)) cols.set(x, []);
        cols.get(x)!.push(y);
    }
    const xs = [...cols.keys()].sort((a, b) => a - b);
    for (const x of xs) cols.get(x)!.sort((a, b) => a - b);
    const arr: number[][] = xs.map(x => cols.get(x)!);

    // first index where Y[i] > v
    const upperBound = (Y: number[], v: number): number => {
        let lo = 0, hi = Y.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (Y[mid] <= v) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    };
    // first index where Y[i] >= v
    const lowerBound = (Y: number[], v: number): number => {
        let lo = 0, hi = Y.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (Y[mid] < v) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    };
    const check = (Y: number[], y1: number, y2: number): boolean => {
        const it = upperBound(Y, y1);
        return it !== Y.length && Y[it] < y2;
    };

    let best = -1;
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            const A = arr[i], B = arr[j];
            const shared: number[] = [];
            let a = 0, b = 0;
            while (a < A.length && b < B.length) {
                if (A[a] === B[b]) { shared.push(A[a]); a++; b++; }
                else if (A[a] < B[b]) a++;
                else b++;
            }
            for (let p = 0; p + 1 < shared.length; p++) {
                const y1 = shared[p], y2 = shared[p + 1];
                let ok = true;
                for (let m = i + 1; m < j && ok; m++) {
                    const Y = arr[m];
                    const it = lowerBound(Y, y1);
                    if (it !== Y.length && Y[it] <= y2) ok = false;
                }
                if (ok && !check(A, y1, y2) && !check(B, y1, y2)) {
                    const dx = xs[j] - xs[i];
                    const area = dx * (y2 - y1);
                    if (area > best) best = area;
                }
            }
        }
    }
    return best;
}