3047. Largest Square Inside Two Rectangles

The 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] and topRight[i] = [c_i, d_i] represent the bottom-left and top-right coordinates of the i^th rectangle, respectively.

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.

Example 1:

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

Output: 1

Explanation:

A square with side length 1 can fit inside either the intersecting region of rectangles 0 and 1 or the intersecting region of rectangles 1 and 2. Hence the maximum area is 1. It can be shown that a square with a greater side length can not fit inside any intersecting region of two rectangles.

Example 2:

Input: bottomLeft = [[1,1],[1,3],[1,5]], topRight = [[5,5],[5,7],[5,9]]

Output: 4

Explanation:

A square with side length 2 can fit inside either the intersecting region of rectangles 0 and 1 or the intersecting region of rectangles 1 and 2. Hence the maximum area is 2 * 2 = 4. It can be shown that a square with a greater side length can not fit inside any intersecting region of two rectangles.

Example 3:

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

Output: 1

Explanation:

A square with side length 1 can fit inside the intersecting region of any two rectangles. Also, no larger square can, so the maximum area is 1. Note that the region can be formed by the intersection of more than 2 rectangles.

Example 4:

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

Output: 0

Explanation:

No pair of rectangles intersect, hence, the answer is 0.

Constraints:

n == bottomLeft.length == topRight.length
2 <= n <= 10³
bottomLeft[i].length == topRight[i].length == 2
1 <= bottomLeft[i][0], bottomLeft[i][1] <= 10⁷
1 <= topRight[i][0], topRight[i][1] <= 10⁷
bottomLeft[i][0] < topRight[i][0]
bottomLeft[i][1] < topRight[i][1]

Approach overview

Problem Overview: You are given multiple axis-aligned rectangles defined by bottom-left and top-right coordinates. For every pair of rectangles, compute their intersection region and determine the largest square that can fit entirely inside that overlap. Return the maximum possible square area among all rectangle pairs.

Approach 1: Brute Force Pair-Wise Intersection Checking (O(n²) time, O(1) space)

Check every pair of rectangles. For each pair, compute the intersection boundaries using left = max(x1a, x1b), right = min(x2a, x2b), bottom = max(y1a, y1b), and top = min(y2a, y2b). If right > left and top > bottom, the rectangles overlap. The largest square inside the overlap has side length min(right - left, top - bottom), and the area is that value squared. Track the maximum area across all pairs. This direct geometric check relies only on coordinate comparisons, making it easy to implement using concepts from geometry and arrays.

Approach 2: Sweep Line Algorithm (O(n log n + k) time, O(n) space)

Sort rectangle edges by their x-coordinates and sweep a vertical line from left to right. Maintain an active set of rectangles whose x-range intersects the sweep line. For rectangles currently active, check overlaps in the y-dimension and compute potential intersection regions. Whenever two rectangles overlap in both x and y, compute the candidate square side using the same min(width, height) rule. Sorting events takes O(n log n), and maintaining active rectangles introduces additional overlap checks. This approach reduces unnecessary comparisons when rectangles are far apart in the plane and is a standard technique in computational geometry problems involving interval intersections.

Recommended for interviews: Start with the brute force pair-wise intersection approach. It clearly demonstrates understanding of rectangle intersection math and runs in O(n^2), which is acceptable for moderate input sizes. If the interviewer pushes for optimization, discuss the sweep line technique that processes rectangles in sorted order and limits comparisons using active intervals.

Approach 1: Brute Force Pair-Wise Intersection Checking

In this approach, we compare each pair of rectangles to determine the maximum possible overlap. We do this to calculate the largest square that can fit within any overlap region of two rectangles. This pairwise comparison, although basic, is manageable for small inputs and will ensure correctness.

Python

def largestSquareArea(bottomLeft, topRight):
    def overlap_area(b1, t1, b2, t2):
        x_overlap = max(0, min(t1[0], t2[0]) - max(b1[0], b2[0]))
        y_overlap = max(0, min(t1[1], t2[1]) - max(b1[1], b2[1]))
        return min(x_overlap, y_overlap) if x_overlap > 0 and y_overlap > 0 else 0

    max_square_side = 0
    n = len(bottomLeft)

    for i in range(n):
        for j in range(i+1, n):
            side = overlap_area(bottomLeft[i], topRight[i], bottomLeft[j], topRight[j])
            max_square_side = max(max_square_side, side)

    return max_square_side ** 2

# Example usage
bottomLeft = [[1,1],[2,2],[3,1]]
topRight = [[3,3],[4,4],[6,6]]
print(largestSquareArea(bottomLeft, topRight))  # Output: 1

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int largestSquareArea(vector<vector<int>>& bottomLeft, vector<vector<int>>& topRight) {
    auto overlap_area = [](const vector<int>& b1, const vector<int>& t1, const vector<int>& b2, const vector<int>& t2) {
        int x_overlap = max(0, min(t1[0], t2[0]) - max(b1[0], b2[0]));
        int y_overlap = max(0, min(t1[1], t2[1]) - max(b1[1], b2[1]));
        return (x_overlap > 0 && y_overlap > 0) ? min(x_overlap, y_overlap) : 0;
    };
    int n = bottomLeft.size();
    int max_square_side = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int side = overlap_area(bottomLeft[i], topRight[i], bottomLeft[j], topRight[j]);
            max_square_side = max(max_square_side, side);
        }
    }
    return max_square_side * max_square_side;
}

int main() {
    vector<vector<int>> bottomLeft = {{1, 1}, {2, 2}, {3, 1}};
    vector<vector<int>> topRight = {{3, 3}, {4, 4}, {6, 6}};
    cout << largestSquareArea(bottomLeft, topRight) << endl; // Output: 1
}

This Python function calculates the largest square area by iterating over all pairs of rectangles and finding their overlapping area. If two rectangles overlap in a region where both dimensions are positive, it calculates the potential square's side length as the minimum of these overlaps. The maximum side length found across all pairs is used to calculate the square area.

Complexity

Time Complexity: O(n^2), as it checks every pair of rectangles.
Space Complexity: O(1), since no extra space is required beyond variables for calculations.

Try this approach in the editor

Approach 2: Using Sweep Line Algorithm

The Sweep Line technique is efficient for interval problems in computational geometry. It entails sorting events and sweeping through them linearly. For this problem, treat rectangle edges as events and evaluate if the regions between these events allow for a larger square. This reduces the number of checks considerably, making the approach more efficient than checking each pair's overlap individually.

Java

import java.util.*;

public class LargestSquare {
    public static int largestSquareArea(int[][] bottomLeft, int[][] topRight) {
        int n = bottomLeft.length;
        List<int[]> events = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            // Start event of the rectangle
            events.add(new int[]{bottomLeft[i][0], bottomLeft[i][1], topRight[i][1], 1});
            // End event of the rectangle
            events.add(new int[]{topRight[i][0], bottomLeft[i][1], topRight[i][1], -1});
        }
        // Sort by x coordinate, and then by type (end before start if same x)
        events.sort((a, b) -> (a[0] == b[0] ? a[3] - b[3] : a[0] - b[0]));

        TreeMap<Integer, Integer> activeY = new TreeMap<>();
        int maxSquareSide = 0;

        for (int i = 0; i < events.size();) {
            int x = events.get(i)[0];
            while (i < events.size() && events.get(i)[0] == x) {
                int yStart = events.get(i)[1], yEnd = events.get(i)[2], type = events.get(i)[3];
                for (int y = yStart; y < yEnd; ++y) {
                    activeY.put(y, activeY.getOrDefault(y, 0) + type);
                    if (activeY.get(y) == 0) {
                        activeY.remove(y);
                    }
                }
                ++i;
            }
            maxSquareSide = max(maxSquareSide, maxSquareRange(activeY));
        }
        return maxSquareSide * maxSquareSide;
    }

    private static int maxSquareRange(TreeMap<Integer, Integer> activeY) {
        int lastY = -1;
        int maxLen = 0;
        int start = -1;
        for (int y : activeY.keySet()) {
            if (activeY.get(y) >= 2) {
                if (start == -1) start = y;
            } else {
                if (start != -1) {
                    maxLen = Math.max(maxLen, y - start);
                    start = -1;
                }
            }
        }
        if (start != -1) {
            maxLen = Math.max(maxLen, activeY.lastKey() + 1 - start);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        int[][] bottomLeft = {{1, 1}, {2, 2}, {3, 1}};
        int[][] topRight = {{3, 3}, {4, 4}, {6, 6}};
        System.out.println(largestSquareArea(bottomLeft, topRight)); // Output: 1
    }
}

JavaScript

function largestSquareArea(bottomLeft, topRight) {
    let n = bottomLeft.length;
    let events = [];
    for (let i = 0; i < n; ++i) {
        events.push([bottomLeft[i][0], 1, bottomLeft[i][1], topRight[i][1]]);
        events.push([topRight[i][0], -1, bottomLeft[i][1], topRight[i][1]]);
    }
    events.sort((a, b) => (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]));

    let activeY = new Map();
    let maxSquareSide = 0;

    for (let i = 0; i < events.length;) {
        let x = events[i][0];
        while (i < events.length && events[i][0] === x) {
            let type = events[i][1];
            let yStart = events[i][2], yEnd = events[i][3];
            for (let y = yStart; y < yEnd; ++y) {
                activeY.set(y, (activeY.get(y) || 0) + type);
                if (activeY.get(y) === 0) {
                    activeY.delete(y);
                }
            }
            ++i;
        }
        maxSquareSide = Math.max(maxSquareSide, maxSquareRange(activeY));
    }
    return maxSquareSide * maxSquareSide;
}

function maxSquareRange(activeY) {
    let lastY = -1;
    let maxLen = 0;
    let start = -1;
    for (let y of activeY.keys()) {
        if (activeY.get(y) >= 2) {
            if (start === -1) start = y;
        } else {
            if (start !== -1) {
                maxLen = Math.max(maxLen, y - start);
                start = -1;
            }
        }
    }
    if (start !== -1) {
        maxLen = Math.max(maxLen, [...activeY.keys()].pop() + 1 - start);
    }
    return maxLen;
}

// Example usage
const bottomLeft = [[1, 1], [2, 2], [3, 1]];
const topRight = [[3, 3], [4, 4], [6, 6]];
console.log(largestSquareArea(bottomLeft, topRight)); // Output: 1

This Java solution uses a sweeping line through the x-axis where events (edges of rectangles) are added and sorted. For each x event, it keeps track of active y-ranges and checks for overlaps. By maintaining this map, it checks if the count of the overlapped ranges allows for placement of a square (requiring at least 2 overlapping rectangles). The solution is optimized using sorting and efficient y-range management, drastically limiting pairwise checks required.

Complexity

Time Complexity: O(n log n), due to sorting events and range queries.
Space Complexity: O(n), for storing events and active areas.

Try this approach in the editor

Approach 3: Enumeration

We can enumerate two rectangles, where the coordinates of the bottom left and top right corners of rectangle 1 are (x_1, y_1) and (x_2, y_2) respectively, and the coordinates of the bottom left and top right corners of rectangle 2 are (x_3, y_3) and (x_4, y_4) respectively.

If rectangle 1 and rectangle 2 intersect, then the coordinates of the intersection are:

The x-coordinate of the bottom left corner is the maximum of the x-coordinates of the bottom left corners of the two rectangles, i.e., max(x_1, x_3);
The y-coordinate of the bottom left corner is the maximum of the y-coordinates of the bottom left corners of the two rectangles, i.e., max(y_1, y_3);
The x-coordinate of the top right corner is the minimum of the x-coordinates of the top right corners of the two rectangles, i.e., min(x_2, x_4);
The y-coordinate of the top right corner is the minimum of the y-coordinates of the top right corners of the two rectangles, i.e., min(y_2, y_4).

Then the width and height of the intersection are w = min(x_2, x_4) - max(x_1, x_3) and h = min(y_2, y_4) - max(y_1, y_3) respectively. We take the minimum of the two as the side length, i.e., e = min(w, h). If e > 0, then we can get a square with an area of e^2. We take the maximum area of all squares.

The time complexity is O(n^2), where n is the number of rectangles. The space complexity is O(1).

TypeScript

function largestSquareArea(bottomLeft: number[][], topRight: number[][]): number {
    let ans = 0;
    for (let i = 0; i < bottomLeft.length; ++i) {
        const [x1, y1] = bottomLeft[i];
        const [x2, y2] = topRight[i];
        for (let j = i + 1; j < bottomLeft.length; ++j) {
            const [x3, y3] = bottomLeft[j];
            const [x4, y4] = topRight[j];
            const w = Math.min(x2, x4) - Math.max(x1, x3);
            const h = Math.min(y2, y4) - Math.max(y1, y3);
            const e = Math.min(w, h);
            if (e > 0) {
                ans = Math.max(ans, e * e);
            }
        }
    }
    return ans;
}

func largestSquareArea(bottomLeft [][]int, topRight [][]int) (ans int64) {
	for i, b1 := range bottomLeft {
		t1 := topRight[i]
		x1, y1 := b1[0], b1[1]
		x2, y2 := t1[0], t1[1]
		for j := i + 1; j < len(bottomLeft); j++ {
			x3, y3 := bottomLeft[j][0], bottomLeft[j][1]
			x4, y4 := topRight[j][0], topRight[j][1]
			w := min(x2, x4) - max(x1, x3)
			h := min(y2, y4) - max(y1, y3)
			e := min(w, h)
			if e > 0 {
				ans = max(ans, int64(e)*int64(e))
			}
		}
	}
	return
}

Rust

impl Solution {
    pub fn largest_square_area(bottom_left: Vec<Vec<i32>>, top_right: Vec<Vec<i32>>) -> i64 {
        let mut ans: i64 = 0;
        let n = bottom_left.len();

        for i in 0..n {
            let x1 = bottom_left[i][0];
            let y1 = bottom_left[i][1];
            let x2 = top_right[i][0];
            let y2 = top_right[i][1];

            for j in (i + 1)..n {
                let x3 = bottom_left[j][0];
                let y3 = bottom_left[j][1];
                let x4 = top_right[j][0];
                let y4 = top_right[j][1];

                let w = (x2.min(x4) - x1.max(x3)) as i64;
                let h = (y2.min(y4) - y1.max(y3)) as i64;
                let e = w.min(h);

                if e > 0 {
                    ans = ans.max(e * e);
                }
            }
        }

        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Brute Force Pair-Wise Intersection Checking	Time Complexity: O(n^2), as it checks every pair of rectangles. Space Complexity: O(1), since no extra space is required beyond variables for calculations.
Using Sweep Line Algorithm	Time Complexity: O(n log n), due to sorting events and range queries. Space Complexity: O(n), for storing events and active areas.
Enumeration	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Pair-Wise Intersection	O(n^2)	O(1)	Small to medium number of rectangles. Simplest implementation for interviews.
Sweep Line Algorithm	O(n log n + k)	O(n)	Large datasets where many rectangles do not overlap. Reduces unnecessary pair checks.

Frequently asked questions

Is Find the Largest Area of Square Inside Two Rectangles easy or hard?

This problem is rated Medium. The geometry for rectangle intersection is straightforward, but recognizing that the square size is limited by the smaller overlap dimension and handling all rectangle pairs correctly requires careful implementation.

Find the Largest Area of Square Inside Two Rectangles Python/Java solution

Python and Java implementations typically compute intersections using coordinate math: left = max(x1a, x1b), right = min(x2a, x2b), bottom = max(y1a, y1b), and top = min(y2a, y2b). If the overlap exists, the square side equals min(right - left, top - bottom) and the area is side^2.

How to solve Find the Largest Area of Square Inside Two Rectangles in O(n)?

Achieving strict O(n) time is generally not feasible because rectangle intersections depend on pair relationships. The closest optimization is a sweep line algorithm with sorting, which runs in O(n log n). It processes rectangles in coordinate order and only checks overlaps among active rectangles.

What is the best approach for Find the Largest Area of Square Inside Two Rectangles?

The most practical approach is pair-wise rectangle intersection checking. For each pair, compute the overlapping region and take the square side as min(overlap width, overlap height). This runs in O(n^2) time and O(1) space and is usually sufficient for interview constraints. For larger inputs, a sweep line technique can reduce unnecessary comparisons.

Is Find the Largest Area of Square Inside Two Rectangles asked at Google/Amazon/Meta?

Problems involving rectangle intersections and sweep line algorithms frequently appear in interviews at companies like Google, Amazon, and Meta. Variations include rectangle overlap detection, skyline problems, and computing intersection areas using geometry or interval sweeps.

What data structure is used in Find the Largest Area of Square Inside Two Rectangles?

The brute force method mainly uses arrays and simple coordinate comparisons. The optimized sweep line approach uses sorted event lists and an active set structure, often implemented with balanced trees or interval lists to track overlapping rectangles during the sweep.

What is the time complexity of Find the Largest Area of Square Inside Two Rectangles?

The straightforward solution checks every pair of rectangles, giving O(n^2) time complexity and O(1) extra space. A sweep line optimization sorts rectangle edges and processes overlaps in roughly O(n log n + k) time, where k is the number of candidate overlaps considered.

Find the Largest Area of Square Inside Two Rectangles solution and explanation

The problem

Approach overview

Approach 1: Brute Force Pair-Wise Intersection Checking

Approach 2: Using Sweep Line Algorithm

Approach 3: Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find the Largest Area of Square Inside Two Rectangles solution and explanation

The problem

Approach overview

Approach 1: Brute Force Pair-Wise Intersection Checking

Approach 2: Using Sweep Line Algorithm

Approach 3: Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems