Find the Largest Area of Square Inside Two Rectangles

Find the Largest Area of Square Inside Two Rectangles - Problem

There exist n rectangles in a 2D plane with edges parallel to the x and y axis. You are given two 2D integer arrays bottomLeft and topRight where:

bottomLeft[i] = [a_i, b_i] represents the bottom-left coordinates of the i-th rectangle

topRight[i] = [c_i, d_i] represents the top-right coordinates of the i-th rectangle

You need to find the maximum area of a square that can fit inside the intersecting region of at least two rectangles. Return 0 if such a square does not exist.

Input & Output

Example 1 — Basic Intersection

$ Input: bottomLeft = [[1,1],[2,2],[3,1]], topRight = [[3,3],[4,4],[4,4]]

› Output: 1

💡 Note: Rectangle 0: (1,1) to (3,3), Rectangle 1: (2,2) to (4,4). Their intersection is (2,2) to (3,3) with width=1, height=1. Largest square has side=1, area=1.

Example 2 — Larger Intersection

$ Input: bottomLeft = [[1,1],[2,2],[1,2]], topRight = [[4,4],[4,4],[3,4]]

› Output: 4

💡 Note: Rectangle 0: (1,1) to (4,4), Rectangle 1: (2,2) to (4,4). Intersection is (2,2) to (4,4) with width=2, height=2. Largest square has side=2, area=4.

Example 3 — No Intersection

$ Input: bottomLeft = [[1,1],[3,3]], topRight = [[2,2],[4,4]]

› Output: 0

💡 Note: Rectangle 0: (1,1) to (2,2), Rectangle 1: (3,3) to (4,4). These rectangles don't intersect, so no square can fit in a shared region.

Constraints

2 ≤ n ≤ 5 × 10⁴
bottomLeft[i].length == topRight[i].length == 2
-10⁹ ≤ bottomLeft[i][j], topRight[i][j] ≤ 10⁹
bottomLeft[i][0] < topRight[i][0] and bottomLeft[i][1] < topRight[i][1]

Visualization

Tap to expand

Understanding the Visualization

Input Rectangles

Given n rectangles with bottom-left and top-right coordinates

Find Intersections

Check all pairs of rectangles to find their overlapping regions

Calculate Largest Square

For each intersection, largest square side = min(width, height)

Key Takeaway

🎯 Key Insight: The largest square in any rectangular intersection has side length equal to the minimum dimension of that intersection

Asked in

G Google 45 a Amazon 32 M Microsoft 28

The key insight is to find all pairwise rectangle intersections and calculate the largest square that fits in each. For each intersection with width W and height H, the largest square has side length min(W,H). Best approach is the optimized O(n²) solution with early termination. Time: O(n²), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Pairs	O(n²)	O(1)	Check every possible pair of rectangles and find their intersection
Optimized Single Pass	O(n²)	O(1)	Same approach but with early termination optimizations

Brute Force - Check All Pairs — Algorithm Steps

Iterate through all pairs of rectangles
Calculate intersection coordinates for each pair
Find minimum dimension (width or height) of intersection
Track maximum square area found

Visualization

Tap to expand

Step-by-Step Walkthrough

Input Rectangles

We have n rectangles defined by bottom-left and top-right coordinates

Check All Pairs

For each pair, calculate intersection bounds and check if valid

Find Largest Square

In each intersection, largest square has side = min(width, height)

Code -

solution.c — C

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

long long solution(int bottomLeft[][2], int topRight[][2], int n) {
    long long maxArea = 0;
    
    // Check all pairs of rectangles
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // Calculate intersection
            int left = (bottomLeft[i][0] > bottomLeft[j][0]) ? bottomLeft[i][0] : bottomLeft[j][0];
            int bottom = (bottomLeft[i][1] > bottomLeft[j][1]) ? bottomLeft[i][1] : bottomLeft[j][1];
            int right = (topRight[i][0] < topRight[j][0]) ? topRight[i][0] : topRight[j][0];
            int top = (topRight[i][1] < topRight[j][1]) ? topRight[i][1] : topRight[j][1];
            
            // Check if intersection exists
            if (left < right && bottom < top) {
                long long width = right - left;
                long long height = top - bottom;
                // Largest square side is minimum of width and height
                long long side = (width < height) ? width : height;
                long long area = side * side;
                maxArea = (maxArea > area) ? maxArea : area;
            }
        }
    }
    
    return maxArea;
}

int main() {
    char line[10000];
    int bottomLeft[1000][2], topRight[1000][2];
    int n = 0;
    
    // Read bottomLeft
    fgets(line, sizeof(line), stdin);
    char* ptr = line + 1; // Skip opening bracket
    while (*ptr != ']' && *ptr != '\0') {
        if (*ptr == '[') {
            ptr++;
            bottomLeft[n][0] = atoi(ptr);
            while (*ptr != ',' && *ptr != '\0') ptr++;
            if (*ptr == ',') ptr++;
            bottomLeft[n][1] = atoi(ptr);
            while (*ptr != ']' && *ptr != '\0') ptr++;
            n++;
        }
        ptr++;
    }
    
    // Read topRight
    fgets(line, sizeof(line), stdin);
    ptr = line + 1; // Skip opening bracket
    int idx = 0;
    while (*ptr != ']' && *ptr != '\0') {
        if (*ptr == '[') {
            ptr++;
            topRight[idx][0] = atoi(ptr);
            while (*ptr != ',' && *ptr != '\0') ptr++;
            if (*ptr == ',') ptr++;
            topRight[idx][1] = atoi(ptr);
            while (*ptr != ']' && *ptr != '\0') ptr++;
            idx++;
        }
        ptr++;
    }
    
    long long result = solution(bottomLeft, topRight, n);
    printf("%lld\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops to check all pairs of n rectangles

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to track coordinates and maximum area

✓ Linear Space

28.4K Views

Medium Frequency

~25 min Avg. Time

890 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 Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler