Maximum Area Rectangle With Point Constraints II

Maximum Area Rectangle With Point Constraints II - Problem

Imagine you're a city planner working with a grid-based map where certain locations are marked as special landmarks. Your task is to find the largest rectangular park that can be built using exactly four of these landmarks as corners.

Given n points on an infinite 2D plane with coordinates (xCoord[i], yCoord[i]), you need to find the maximum area rectangle that:

Uses exactly four points as its corners
Has edges parallel to the axes (axis-aligned)
Contains no other points inside or on its borders

Return the maximum area possible, or -1 if no valid rectangle can be formed.

Example: With points [(1,1), (1,3), (3,1), (3,3), (2,2)], the rectangle with corners (1,1), (1,3), (3,1), (3,3) would be invalid because (2,2) lies inside it.

Input & Output

Constraints

Asked in

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force (Check All 4-Point Combinations)	O(n^5)	O(1)	Try every combination of 4 points to see if they form a valid axis-aligned rectangle
Diagonal Pairs Approach	O(n³)	O(n)	First store all points in hash set, then check diagonal pairs for valid rectangles
Coordinate Compression + Sweep Line	O(n² log n)	O(n)	Use coordinate compression and sweep line algorithm for optimal rectangle detection

Brute Force (Check All 4-Point Combinations) — Algorithm Steps

Generate all C(n,4) combinations of 4 points
For each combination, check if points form an axis-aligned rectangle
If valid rectangle, check that no other points lie inside or on border
Track maximum area found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate 4-point combinations

Use nested loops to try all C(n,4) combinations

Check if points form rectangle

Verify the 4 points can form an axis-aligned rectangle

Validate empty interior

Ensure no other points lie inside the rectangle

Track maximum area

Keep the largest valid rectangle found

Code -

solution.c — C

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

int compare(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

int largestRectangleArea(int* xCoord, int xCoordSize, int* yCoord, int yCoordSize) {
    int n = xCoordSize;
    if (n < 4) return -1;
    
    int maxArea = -1;
    
    // Try all combinations of 4 points
    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 xs[4] = {xCoord[i], xCoord[j], xCoord[k], xCoord[l]};
                    int ys[4] = {yCoord[i], yCoord[j], yCoord[k], yCoord[l]};
                    qsort(xs, 4, sizeof(int), compare);
                    qsort(ys, 4, sizeof(int), compare);
                    
                    if (xs[0] != xs[1] || xs[2] != xs[3] || ys[0] != ys[1] || ys[2] != ys[3]) continue;
                    if (xs[1] == xs[2] || ys[1] == ys[2]) continue;
                    
                    int x1 = xs[0], x2 = xs[2];
                    int y1 = ys[0], y2 = ys[2];
                    
                    // Check if we have all 4 corners (simplified check for C)
                    int cornerCount = 0;
                    int indices[4] = {i, j, k, l};
                    for (int idx = 0; idx < 4; idx++) {
                        int px = xCoord[indices[idx]];
                        int py = yCoord[indices[idx]];
                        if ((px == x1 && py == y1) || (px == x1 && py == y2) || 
                            (px == x2 && py == y1) || (px == x2 && py == y2)) {
                            cornerCount++;
                        }
                    }
                    if (cornerCount != 4) continue;
                    
                    // Check no other points inside or on border
                    int valid = 1;
                    for (int m = 0; m < n; m++) {
                        if (m == i || m == j || m == k || m == l) continue;
                        if (xCoord[m] >= x1 && xCoord[m] <= x2 && yCoord[m] >= y1 && yCoord[m] <= y2) {
                            valid = 0;
                            break;
                        }
                    }
                    
                    if (valid) {
                        int area = (x2 - x1) * (y2 - y1);
                        if (area > maxArea) {
                            maxArea = area;
                        }
                    }
                }
            }
        }
    }
    
    return maxArea;
}

Time & Space Complexity

Time Complexity

⏱️

O(n^5)

O(n^4) to check all 4-point combinations, O(n) to verify each rectangle is empty

✓ Linear Growth

Space Complexity

O(1)

Only storing constant amount of variables

✓ Linear Space

25.0K Views

Medium Frequency

~15 min Avg. Time

850 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