Skip to main content
Talentd

Find the Largest Area of Square Inside Two Rectangles - Solution & Explanation

MediumArrayMathGeometry17 min readAsked at: Microsoft, Meta, Cisco +2
Practice this problem

Problem Statement

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 ith 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 <= 103
  • bottomLeft[i].length == topRight[i].length == 2
  • 1 <= bottomLeft[i][0], bottomLeft[i][1] <= 107
  • 1 <= topRight[i][0], topRight[i][1] <= 107
  • 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(n2) 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.

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.

Code

PythonC++

Python

C++

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.

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.

Code

JavaJavaScript

Java

JavaScript

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).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

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

Video Solution

Find the Largest Area of Square Inside Two Rectangles | Simple | Intuitive | Leetcode 3047 | MIK • codestorywithMIK • 7,854 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Find the Largest Area of Square Inside Two Rectangles with our built-in code editor and test cases.

Practice on FleetCode
Previous

Rectangle Area