Maximum Area Rectangle With Point Constraints I

Maximum Area Rectangle With Point Constraints I - Problem

Array Math Binary Indexed Tree Segment Tree Geometry Sorting Enumeration Medium

You are given an array points where points[i] = [xi, yi] represents the coordinates of a point on an infinite plane.

Your task is to find the maximum area of a rectangle that:

Can be formed using four of these points as its corners
Does not contain any other point inside or on its border
Has its edges parallel to the axes

Return the maximum area that you can obtain or -1 if no such rectangle is possible.

Input & Output

Example 1 — Valid Rectangle Found

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

› Output: 4

💡 Note: Points [1,1], [1,3], [3,1], [3,3] form a 2×2 rectangle with area 4. Point [2,2] is inside, so this rectangle is invalid. No other valid rectangles exist, but let's say we had points without [2,2] - then area would be 4.

Example 2 — No Valid Rectangle

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

› Output: -1

💡 Note: The only potential rectangle has point [2,2] inside it, making it invalid. No other combination of 4 points can form a valid rectangle.

Example 3 — Multiple Valid Rectangles

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

› Output: 4

💡 Note: Two valid rectangles: [1,1],[1,3],[3,1],[3,3] with area 4, and [4,4],[4,6],[6,4],[6,6] with area 4. Maximum area is 4.

Constraints

4 ≤ points.length ≤ 3000
-10⁵ ≤ xi, yi ≤ 10⁵
All points are distinct

Visualization

Tap to expand

Understanding the Visualization

Input Points

Given set of coordinate points on a plane

Find Rectangles

Identify all possible axis-aligned rectangles using 4 points

Validate & Maximize

Ensure no points inside, return maximum area or -1

Key Takeaway

🎯 Key Insight: Use diagonal point pairs to efficiently validate rectangles instead of checking all 4-point combinations

Asked in

G Google 25 M Microsoft 18 a Amazon 15 f Meta 12

The key insight is to recognize that a valid rectangle needs exactly 4 corner points with no other points inside or on the border. The optimal approach uses diagonal pairs to reduce from O(n⁴) brute force to O(n³) by checking only O(n²) potential diagonal combinations. Time: O(n³), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Sweep Optimization	O(n³)	O(n)	Use coordinate sorting and sweep line to reduce validation overhead
Brute Force - Check All Combinations	O(n⁴)	O(1)	Try every possible combination of 4 points to form rectangles

Sort and Sweep Optimization — Algorithm Steps

Sort all points by coordinates
For each pair of points as potential diagonal
Check if other two corners exist in point set
Use coordinate bounds to efficiently check interior points

Visualization

Tap to expand

Step-by-Step Walkthrough

Pick Diagonal

Select two points as potential diagonal corners

Find Corners

Check if the other two corners exist in point set

Validate

Ensure no points inside the formed rectangle

Code -

solution.c — C

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

typedef struct {
    char key[20];
    int exists;
} PointMap;

int findInMap(PointMap* map, int size, const char* key) {
    for (int i = 0; i < size; i++) {
        if (strcmp(map[i].key, key) == 0) {
            return map[i].exists;
        }
    }
    return 0;
}

void addToMap(PointMap* map, int* size, const char* key) {
    strcpy(map[*size].key, key);
    map[*size].exists = 1;
    (*size)++;
}

int solution(int points[][2], int n) {
    if (n < 4) return -1;
    
    PointMap pointMap[1000];
    int mapSize = 0;
    
    // Build point map
    for (int i = 0; i < n; i++) {
        char key[20];
        sprintf(key, "%d,%d", points[i][0], points[i][1]);
        addToMap(pointMap, &mapSize, key);
    }
    
    int maxArea = -1;
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int x1 = points[i][0], y1 = points[i][1];
            int x2 = points[j][0], y2 = points[j][1];
            
            if (x1 == x2 || y1 == y2) continue;
            
            char corner1[20], corner2[20];
            sprintf(corner1, "%d,%d", x1, y2);
            sprintf(corner2, "%d,%d", x2, y1);
            
            if (findInMap(pointMap, mapSize, corner1) && findInMap(pointMap, mapSize, corner2)) {
                int minX = x1 < x2 ? x1 : x2;
                int maxX = x1 > x2 ? x1 : x2;
                int minY = y1 < y2 ? y1 : y2;
                int maxY = y1 > y2 ? y1 : y2;
                
                char corners[4][20];
                sprintf(corners[0], "%d,%d", minX, minY);
                sprintf(corners[1], "%d,%d", minX, maxY);
                sprintf(corners[2], "%d,%d", maxX, minY);
                sprintf(corners[3], "%d,%d", maxX, maxY);
                
                int valid = 1;
                for (int k = 0; k < n && valid; k++) {
                    char key[20];
                    sprintf(key, "%d,%d", points[k][0], points[k][1]);
                    
                    int isCorner = 0;
                    for (int l = 0; l < 4; l++) {
                        if (strcmp(key, corners[l]) == 0) {
                            isCorner = 1;
                            break;
                        }
                    }
                    if (isCorner) continue;
                    
                    if (points[k][0] >= minX && points[k][0] <= maxX && 
                        points[k][1] >= minY && points[k][1] <= maxY) {
                        valid = 0;
                    }
                }
                
                if (valid) {
                    int area = (maxX - minX) * (maxY - minY);
                    if (area > maxArea) maxArea = area;
                }
            }
        }
    }
    
    return maxArea;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int points[1000][2];
    int n = 0;
    
    char *ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            points[n][0] = strtol(ptr, &ptr, 10);
            ptr++;
            points[n][1] = strtol(ptr, &ptr, 10);
            n++;
            ptr++;
        }
        ptr++;
    }
    
    printf("%d\n", solution(points, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n²) pairs of potential diagonal points, O(n) validation per pair

⚠ Quadratic Growth

Space Complexity

O(n)

Hash set to store all points for O(1) corner existence checks

⚡ Linearithmic Space

8.4K Views

Medium Frequency

~35 min Avg. Time

245 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

Sort and Sweep Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler