Minimum Area Rectangle II - Problem

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 any rectangle formed from these points, with sides not necessarily parallel to the X and Y axes.

If there is no such rectangle, return 0.

Answers within 10^-5 of the actual answer will be accepted.

Input & Output

Example 1 — Basic Rectangle

$ Input: points = [[1,2],[2,1],[1,0],[0,1]]

› Output: 2.0

💡 Note: These 4 points form a square rotated 45 degrees with side length √2, so area = (√2)² = 2.0

Example 2 — No Rectangle

$ Input: points = [[1,1],[1,3],[3,1]]

› Output: 0.0

💡 Note: Only 3 points given, cannot form any rectangle, return 0

Example 3 — Multiple Rectangles

$ Input: points = [[0,0],[1,0],[2,0],[0,1],[1,1],[2,1]]

› Output: 1.0

💡 Note: Multiple rectangles possible, smallest has area 1.0 (1×1 square)

Constraints

1 ≤ points.length ≤ 50
points[i].length == 2
0 ≤ x_i, y_i ≤ 4 × 10⁴
All the given points are unique

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 8 M Microsoft 12

The key insight is to use rectangle properties - diagonals bisect each other and are equal in length. For each pair of points as diagonal corners, calculate the center and find the other two corners using 90-degree rotation. Best approach is the diagonal-based method. Time: O(n²), Space: O(n)

Common Approaches

✓ Brute Force - Check All Combinations

⏱️ Time: O(n⁴) Space: O(1)

Generate all possible combinations of 4 points from the input and check if they form a valid rectangle by verifying that opposite sides are equal and parallel, and all angles are 90 degrees.

Diagonal-Based Approach

⏱️ Time: O(n²) Space: O(n)

Use the property that in a rectangle, diagonals bisect each other and are equal in length. For each pair of points as potential diagonal, calculate the center and find other points that would form a rectangle.

Brute Force - Check All Combinations — Algorithm Steps

Step 1: Generate all combinations of 4 points from the input array
Step 2: For each combination, check if the 4 points form a rectangle
Step 3: Calculate area of valid rectangles and track the minimum

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Combinations

Create all possible groups of 4 points

Rectangle Check

Verify if 4 points form a valid rectangle

Track Minimum

Keep the smallest area found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <float.h>

double integerSqrt(double x) {
    if (x < 0) return 0;
    if (x < 1) return x;
    
    double guess = x / 2.0;
    double prev = 0;
    
    while (guess != prev) {
        prev = guess;
        guess = (guess + x / guess) / 2.0;
        if ((guess - prev < 1e-12) && (prev - guess < 1e-12)) break;
    }
    
    return guess;
}

double fabs_custom(double x) {
    return x < 0 ? -x : x;
}

typedef struct {
    int valid;
    double area;
} RectResult;

double distanceSquared(int p1[], int p2[]) {
    double dx = p1[0] - p2[0];
    double dy = p1[1] - p2[1];
    return dx * dx + dy * dy;
}

RectResult isRectangleAndArea(int p1[], int p2[], int p3[], int p4[]) {
    int* pts[4] = {p1, p2, p3, p4};
    RectResult result = {0, 0.0};
    
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (i == j) continue;
            for (int k = 0; k < 4; k++) {
                if (k == i || k == j) continue;
                for (int l = 0; l < 4; l++) {
                    if (l == i || l == j || l == k) continue;
                    
                    int* A = pts[i];
                    int* B = pts[j];
                    int* C = pts[k];
                    int* D = pts[l];
                    
                    double AB_sq = distanceSquared(A, B);
                    double BC_sq = distanceSquared(B, C);
                    double CD_sq = distanceSquared(C, D);
                    double DA_sq = distanceSquared(D, A);
                    double AC_sq = distanceSquared(A, C);
                    double BD_sq = distanceSquared(B, D);
                    
                    double eps = 1e-9;
                    
                    // Check: opposite sides equal and diagonals equal
                    if (fabs_custom(AB_sq - CD_sq) < eps && 
                        fabs_custom(BC_sq - DA_sq) < eps && 
                        fabs_custom(AC_sq - BD_sq) < eps) {
                        
                        // Check perpendicularity of adjacent sides AB and BC only
                        double AB_x = B[0] - A[0];
                        double AB_y = B[1] - A[1];
                        double BC_x = C[0] - B[0];
                        double BC_y = C[1] - B[1];
                        double dot_product = AB_x * BC_x + AB_y * BC_y;
                        
                        if (fabs_custom(dot_product) < eps) {
                            double side1 = integerSqrt(AB_sq);
                            double side2 = integerSqrt(BC_sq);
                            result.valid = 1;
                            result.area = side1 * side2;
                            return result;
                        }
                    }
                }
            }
        }
    }
    
    return result;
}

double solution(int** points, int pointsSize) {
    if (pointsSize < 4) return 0.0;
    
    double minArea = DBL_MAX;
    
    for (int i = 0; i < pointsSize; i++) {
        for (int j = i + 1; j < pointsSize; j++) {
            for (int k = j + 1; k < pointsSize; k++) {
                for (int l = k + 1; l < pointsSize; l++) {
                    RectResult result = isRectangleAndArea(points[i], points[j], points[k], points[l]);
                    if (result.valid) {
                        if (result.area < minArea) {
                            minArea = result.area;
                        }
                    }
                }
            }
        }
    }
    
    return minArea == DBL_MAX ? 0.0 : minArea;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int** points = malloc(1000 * sizeof(int*));
    int pointsSize = 0;
    
    // Find the start of the array
    char* start = strchr(line, '[');
    if (start == NULL) {
        printf("0.0\n");
        free(points);
        return 0;
    }
    
    start++; // Move past the opening bracket
    char* ptr = start;
    
    while (*ptr != '\0' && *ptr != ']') {
        // Skip whitespace
        while (*ptr == ' ' || *ptr == '\t' || *ptr == '\n') ptr++;
        
        if (*ptr == '[') {
            // Found start of a point
            ptr++; // Skip '['
            
            points[pointsSize] = malloc(2 * sizeof(int));
            
            // Parse first number
            char* endptr;
            points[pointsSize][0] = strtol(ptr, &endptr, 10);
            ptr = endptr;
            
            // Skip comma and whitespace
            while (*ptr == ',' || *ptr == ' ' || *ptr == '\t') ptr++;
            
            // Parse second number
            points[pointsSize][1] = strtol(ptr, &endptr, 10);
            ptr = endptr;
            
            // Skip to closing bracket
            while (*ptr != ']' && *ptr != '\0') ptr++;
            if (*ptr == ']') ptr++; // Skip ']'
            
            pointsSize++;
        } else if (*ptr == ',') {
            ptr++;
        } else {
            ptr++;
        }
    }
    
    printf("%.1f\n", solution(points, pointsSize));
    
    for (int i = 0; i < pointsSize; i++) {
        free(points[i]);
    }
    free(points);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n⁴)

Four nested loops to check all combinations of 4 points

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for calculations

✓ Linear Space

28.1K Views

Medium Frequency

~25 min Avg. Time

834 Likes

Ln 1, Col 1

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Minimum Area Rectangle II - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler