Minimum Area Rectangle II - Practice Coding Problems

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

Understanding the Visualization

Input Points

Given array of coordinate points in 2D plane

Find Rectangles

Identify all valid rectangles (any orientation)

Return Minimum

Calculate and return the smallest area found

Key Takeaway

🎯 Key Insight: Use the fact that rectangle diagonals bisect each other to efficiently find all valid rectangles

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

Approach	Time	Space	Notes
✓ Brute Force - Check All Combinations	O(n⁴)	O(1)	Try every combination of 4 points and verify if they form a rectangle
Diagonal-Based Approach	O(n²)	O(n)	For each pair of points as diagonal, find other two points that complete the 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 <math.h>
#include <string.h>
#include <float.h>

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

int compareDoubles(const void *a, const void *b) {
    double da = *(const double*)a;
    double db = *(const double*)b;
    return (da > db) - (da < db);
}

int isRectangle(int p1[], int p2[], int p3[], int p4[]) {
    int* pts[4] = {p1, p2, p3, p4};
    double distances[6];
    int idx = 0;
    
    for (int i = 0; i < 4; i++) {
        for (int j = i + 1; j < 4; j++) {
            distances[idx++] = distance(pts[i], pts[j]);
        }
    }
    
    qsort(distances, 6, sizeof(double), compareDoubles);
    
    return fabs(distances[0] - distances[1]) < 1e-9 &&
           fabs(distances[2] - distances[3]) < 1e-9 &&
           fabs(distances[4] - distances[5]) < 1e-9;
}

double rectangleArea(int p1[], int p2[], int p3[], int p4[]) {
    int* pts[4] = {p1, p2, p3, p4};
    double distances[6];
    int idx = 0;
    
    for (int i = 0; i < 4; i++) {
        for (int j = i + 1; j < 4; j++) {
            distances[idx++] = distance(pts[i], pts[j]);
        }
    }
    
    qsort(distances, 6, sizeof(double), compareDoubles);
    return distances[0] * distances[2];
}

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++) {
                    if (isRectangle(points[i], points[j], points[k], points[l])) {
                        double area = rectangleArea(points[i], points[j], points[k], points[l]);
                        if (area < minArea) {
                            minArea = area;
                        }
                    }
                }
            }
        }
    }
    
    return minArea == DBL_MAX ? 0.0 : minArea;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [[x1,y1],[x2,y2],...]
    int** points = malloc(1000 * sizeof(int*));
    int pointsSize = 0;
    
    char* ptr = strchr(line, '[');
    while (ptr && (ptr = strchr(ptr + 1, '['))) {
        points[pointsSize] = malloc(2 * sizeof(int));
        sscanf(ptr + 1, "%d,%d", &points[pointsSize][0], &points[pointsSize][1]);
        pointsSize++;
        ptr = strchr(ptr, ']');
    }
    
    printf("%f\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.0K Views

Medium Frequency

~25 min Avg. Time

834 Likes

Ln 1, Col 1

Smart Actions

💡 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler