939. Minimum Area Rectangle

You are given an array of points in the X-Y plane points where $points[i]=[x_i,y_i]$.

Return the minimum area of a rectangle formed from these points, with sides parallel to the X and Y axes. If there is not any such rectangle, return 0.
 

Example 1:

Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4

Example 2:

Input: points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Output: 2

Constraints:

• 1 <= points.length <= 500
• points[i].length == 2
• $0<=x_i,y_i<=4\ast 10^4$
• All the given points are unique.

From: LeetCode
Link: 939. Minimum Area Rectangle

Solution:

Ideas:

Sort all points by (x,y). For every pair of points that could be opposite corners (different x and y), binary-search the existence of the other two required corners. Track the minimum area. Time O(N^2 log N), space O(1) extra.

Code:

typedef struct { int x, y; } Point;

static int cmpPoint(const void *a, const void *b) {
    const Point *p = (const Point *)a, *q = (const Point *)b;
    if (p->x != q->x) return (p->x < q->x) ? -1 : 1;
    if (p->y != q->y) return (p->y < q->y) ? -1 : 1;
    return 0;
}

// binary search for (x,y) in a sorted array `arr` of size n
static int exists(Point *arr, int n, int x, int y) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (arr[mid].x == x && arr[mid].y == y) return 1;
        if (arr[mid].x < x || (arr[mid].x == x && arr[mid].y < y)) lo = mid + 1;
        else hi = mid - 1;
    }
    return 0;
}

int minAreaRect(int** points, int pointsSize, int* pointsColSize) {
    (void)pointsColSize;

    if (pointsSize < 4) return 0;

    // copy to a flat array and sort for O(log N) lookups
    Point *arr = (Point *)malloc(pointsSize * sizeof(Point));
    for (int i = 0; i < pointsSize; ++i) {
        arr[i].x = points[i][0];
        arr[i].y = points[i][1];
    }
    qsort(arr, pointsSize, sizeof(Point), cmpPoint);

    int ans = 0;                 // 0 means "not found yet"
    for (int i = 0; i < pointsSize; ++i) {
        for (int j = i + 1; j < pointsSize; ++j) {
            if (arr[i].x == arr[j].x || arr[i].y == arr[j].y) continue; // not diagonal corners
            // check if the other two corners exist
            if (exists(arr, pointsSize, arr[i].x, arr[j].y) &&
                exists(arr, pointsSize, arr[j].x, arr[i].y)) {
                int area = abs(arr[i].x - arr[j].x) * abs(arr[i].y - arr[j].y);
                if (ans == 0 || area < ans) ans = area;
            }
        }
    }

    free(arr);
    return ans; // 0 if no axis-aligned rectangle exists
}