Find the Largest Area of Square Inside Two Rectangles

Find the Largest Area of Square Inside Two Rectangles

What is this problem about?

The Find the Largest Area of Square Inside Two Rectangles interview question is a geometry task. You are given two sets of rectangles (or pairs of rectangles). Your goal is to find the largest square that can fit inside the intersection of any two rectangles (one from each set, or any two from a single set depending on the variant). You need to return the area of that square.

Why is this asked in interviews?

Companies like Cisco and Google ask the Find the Largest Area coding problem to test your ability to calculate intersections in a 2D coordinate system. It evaluations your skills in Geometry and Array interview patterns, specifically how to find the overlap of two intervals on the X and Y axes independently.

Algorithmic pattern used

This problem follows the Interval Intersection pattern.

1. Find Overlap: For two rectangles $A$ and $B$:

• The X-overlap length is $L_x = \max(0, \min(A.x2, B.x2) - \max(A.x1, B.x1))$.
• The Y-overlap length is $L_y = \max(0, \min(A.y2, B.y2) - \max(A.y1, B.y1))$.

1. Max Square Side: The largest square that fits in this $L_x imes L_y$ intersection has a side length $S = \min(L_x, L_y)$.
2. Iterate: Check all pairs of rectangles and track the maximum $S$ found.
3. Area: Result is $S^2$.

Example explanation

Rect 1: (0,0) to (5,5), Rect 2: (2,2) to (8,8)

1. X-range: [0, 5] and [2, 8]. Overlap: [2, 5]. $L_x = 3$.
2. Y-range: [0, 5] and [2, 8]. Overlap: [2, 5]. $L_y = 3$.
3. Side $S = \min(3, 3) = 3$. Area = 9.

Common mistakes candidates make

• Wrong Intersection Logic: Using min(max) instead of max(min) for the boundaries of the overlap.
• Area vs Side: Forgetting to take the minimum of the two dimensions. A $10 imes 2$ intersection can only hold a $2 imes 2$ square.
• $O(N^2)$ Complexity: If there are $10^5$ rectangles, a nested loop won't work. You might need a sweep-line or a segment tree (though usually $N$ is small for this variant).

Interview preparation tip

Remember the formula for the intersection of two 1D intervals $[a, b]$ and $[c, d]$ is $[\max(a, c), \min(b, d)]$. If $\max > \min$, there is no overlap. This is the foundation for all 2D bounding-box problems.