Minimum Area Rectangle - Practice Coding Problems

Minimum Area Rectangle - Problem

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

Return the minimum area of a rectangle formed from these points, with sides parallel to the X and Y axes.

If there is no such rectangle, return 0.

Input & Output

Example 1 — Basic Rectangle

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

› Output: 4

💡 Note: The four points form a rectangle with corners at (1,1), (1,3), (3,1), (3,3). Width = 3-1 = 2, Height = 3-1 = 2, Area = 2×2 = 4.

Example 2 — Multiple Rectangles

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

› Output: 4

💡 Note: Even with an extra point (2,2), the same rectangle from example 1 is still the only valid rectangle, so minimum area remains 4.

Example 3 — No Rectangle Possible

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

› Output: 0

💡 Note: Only 3 points provided. Need at least 4 points to form a rectangle, so return 0.

Constraints

1 ≤ points.length ≤ 500
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 set of coordinate points

Find Rectangles

Identify all possible rectangles with axis-parallel sides

Minimum Area

Return the smallest rectangle area

Key Takeaway

🎯 Key Insight: A rectangle is uniquely determined by two diagonal points - use this to reduce from O(n⁴) to O(n²)

Asked in

G Google 45 f Facebook 38 a Amazon 32 M Microsoft 28

The key insight is that a rectangle is uniquely determined by its two diagonal points. Instead of checking all combinations of 4 points, we can check all pairs of points as potential diagonals. Best approach uses hash set lookup in O(n²) time with O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Point Combinations	O(n⁴)	O(1)	Check every combination of 4 points to see if they form a rectangle
Two Diagonal Points Approach	O(n²)	O(n)	For each pair of points as diagonal, check if other two corners exist

Brute Force - Check All Point Combinations — Algorithm Steps

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

Visualization

Tap to expand

Step-by-Step Walkthrough

Select 4 Points

Pick any 4 points from the input

Check Rectangle

Verify if these 4 points form a valid rectangle

Calculate Area

If valid, compute area and track minimum

Code -

solution.c — C

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

int getRectangleArea(int rectPoints[4][2]) {
    // Simple bubble sort for 4 points
    for (int i = 0; i < 3; i++) {
        for (int j = i + 1; j < 4; j++) {
            if (rectPoints[i][0] > rectPoints[j][0] || 
                (rectPoints[i][0] == rectPoints[j][0] && rectPoints[i][1] > rectPoints[j][1])) {
                int temp[2] = {rectPoints[i][0], rectPoints[i][1]};
                rectPoints[i][0] = rectPoints[j][0];
                rectPoints[i][1] = rectPoints[j][1];
                rectPoints[j][0] = temp[0];
                rectPoints[j][1] = temp[1];
            }
        }
    }
    
    int x1 = rectPoints[0][0], y1 = rectPoints[0][1];
    int x2 = rectPoints[1][0], y2 = rectPoints[1][1];
    int x3 = rectPoints[2][0], y3 = rectPoints[2][1];
    int x4 = rectPoints[3][0], y4 = rectPoints[3][1];
    
    if ((x1 == x2 && x3 == x4 && y1 == y3 && y2 == y4) ||
        (x1 == x3 && x2 == x4 && y1 == y2 && y3 == y4)) {
        int width = abs(x4 - x1);
        int height = abs(y4 - y1);
        return width * height;
    }
    
    return 0;
}

int solution(int points[][2], int n) {
    if (n < 4) return 0;
    
    int minArea = INT_MAX;
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                for (int l = k + 1; l < n; l++) {
                    int rectPoints[4][2] = {
                        {points[i][0], points[i][1]},
                        {points[j][0], points[j][1]},
                        {points[k][0], points[k][1]},
                        {points[l][0], points[l][1]}
                    };
                    int area = getRectangleArea(rectPoints);
                    if (area > 0 && area < minArea) {
                        minArea = area;
                    }
                }
            }
        }
    }
    
    return minArea == INT_MAX ? 0 : minArea;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int points[1000][2];
    int n = 0;
    
    char *ptr = strchr(line, '[');
    while (ptr && (ptr = strchr(ptr + 1, '['))) {
        int x, y;
        if (sscanf(ptr, "[%d,%d]", &x, &y) == 2) {
            points[n][0] = x;
            points[n][1] = y;
            n++;
        }
    }
    
    int result = solution(points, n);
    printf("%d\n", result);
    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

✓ Linear Space

67.5K Views

Medium Frequency

~25 min Avg. Time

887 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 Point Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler