# Find the Largest Area of Square Inside Two Rectangles
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-largest-area-of-square-inside-two-rectangles)
Canonical: https://scaleengineer.com/dsa/problems/find-the-largest-area-of-square-inside-two-rectangles
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry)
**Data structures:** Array
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco)
---
## 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 `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:**

![](https://assets.glich.co/dsa/find-the-largest-area-of-square-inside-two-rectangles/image0.png) 

**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:**

![](https://assets.glich.co/dsa/find-the-largest-area-of-square-inside-two-rectangles/image1.png) 

**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:**

`![](https://assets.glich.co/dsa/find-the-largest-area-of-square-inside-two-rectangles/image2.png) ` 

**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:**

`![](https://assets.glich.co/dsa/find-the-largest-area-of-square-inside-two-rectangles/image3.png) ` 

**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]`

# Approaches
## Brute-Force Over Larger Groups
A naive approach is to interpret the condition "at least two rectangles" as a need to check intersections of groups of two, three, or more rectangles. This method exhaustively checks all pairs and triples of rectangles, calculates the largest square that can fit in their common intersection, and finds the overall maximum. While correct, this approach performs a significant amount of unnecessary work.
**Time:** O(N^3), where N is the number of rectangles. The three nested loops to iterate through all triples of rectangles dominate the runtime. · **Space:** O(1) extra space, as it only requires a few variables to store the maximum side and intermediate intersection coordinates.
**Pros:** Conceptually simple to extend from a pairwise check.; Guaranteed to be correct, as it checks all required conditions and more.
**Cons:** Highly inefficient with a time complexity of O(N^3).; The logic for checking triples is redundant, as the intersection of three rectangles is always a subset of the intersection of any two of them. This means a triple intersection can never yield a larger square than a pairwise one.
### Explanation
This approach is a brute-force method that considers more combinations than necessary. The algorithm proceeds as follows:

1.  Initialize a variable `maxSide` to 0, which will store the side length of the largest square found so far.
2.  First, it iterates through all unique pairs of rectangles `(i, j)`. For each pair, it computes their intersection. The intersection of two rectangles `R_i = (x1i, y1i, x2i, y2i)` and `R_j = (x1j, y1j, x2j, y2j)` is a new rectangle with its bottom-left corner at `(max(x1i, x1j), max(y1i, y1j))` and its top-right corner at `(min(x2i, x2j), min(y2i, y2j))`. If this intersection is valid (i.e., its width and height are positive), we find the side of the largest square it can contain, which is `min(width, height)`. We update `maxSide` with this value if it's larger.
3.  Next, the algorithm iterates through all unique triples of rectangles `(i, j, k)`. It finds their common intersection, for instance, by first intersecting `R_i` and `R_j`, and then intersecting the resulting rectangle with `R_k`. Similar to the pairwise case, it calculates the largest square in this triple intersection and updates `maxSide`.
4.  The final result is the area of the square with the side `maxSide`, which is `maxSide * maxSide`.

This method is fundamentally flawed in terms of efficiency because the work done checking triples is redundant. Any square that fits in the intersection of three rectangles `R_i, R_j, R_k` also fits in the intersection of any pair from that triple (e.g., `R_i` and `R_j`). Thus, the maximum square side will always be found by considering only pairs.

```java
// Snippet demonstrating the inefficient triple loop logic
long maxSide = 0;
int n = bottomLeft.length;
// O(N^2) part for pairs (essential)
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        // ... pairwise intersection calculation ...
        // maxSide = max(maxSide, side_from_pair_ij);
    }
}

// O(N^3) part for triples (inefficient and redundant)
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        for (int k = j + 1; k < n; k++) {
            // Find intersection of i and j
            long ix1 = Math.max(bottomLeft[i][0], bottomLeft[j][0]);
            long iy1 = Math.max(bottomLeft[i][1], bottomLeft[j][1]);
            long ix2 = Math.min(topRight[i][0], topRight[j][0]);
            long iy2 = Math.min(topRight[i][1], topRight[j][1]);

            // Intersect with k
            ix1 = Math.max(ix1, bottomLeft[k][0]);
            iy1 = Math.max(iy1, bottomLeft[k][1]);
            ix2 = Math.min(ix2, topRight[k][0]);
            iy2 = Math.min(iy2, topRight[k][1]);

            if (ix2 > ix1 && iy2 > iy1) {
                long side = Math.min(ix2 - ix1, iy2 - iy1);
                maxSide = Math.max(maxSide, side);
            }
        }
    }
}
// return maxSide * maxSide;
```
### Algorithm
*   Initialize a variable `maxSide` to 0.
*   Use a nested loop to iterate through all unique pairs of rectangles `(i, j)`.
*   For each pair, calculate the coordinates of their intersection rectangle.
*   If the intersection is valid (has positive width and height), calculate the side `s` of the largest square that can fit inside (`s = min(width, height)`).
*   Update `maxSide = max(maxSide, s)`.
*   Use a third nested loop to iterate through all unique triples of rectangles `(i, j, k)`.
*   For each triple, calculate their common intersection.
*   If the intersection is valid, calculate the side `s` of the largest square and update `maxSide` accordingly.
*   After all loops complete, return the area, which is `(long)maxSide * maxSide`.

## Efficient Pairwise Comparison
This approach is based on the key insight that the largest square must be contained within the intersection of some set of rectangles. Crucially, if a square fits into the intersection of `k` rectangles, it must also fit into the intersection of any two of those `k` rectangles. This means we only need to find the maximum square for all pairwise intersections; checking larger groups is redundant. This simplifies the problem to iterating through all pairs of rectangles, calculating their intersection, and finding the largest possible square within that intersection.
**Time:** O(N^2), where N is the number of rectangles. There are two nested loops to iterate through all N*(N-1)/2 unique pairs of rectangles. The calculations inside the loops take constant time. · **Space:** O(1) extra space. The algorithm only uses a few variables to store the maximum side length and intermediate coordinates, regardless of the input size.
**Pros:** Optimal time complexity for a direct comparison-based method.; Simple to understand and implement correctly.; Efficient enough to pass within the time limits for the given constraints (N <= 1000).
**Cons:** The O(N^2) time complexity might be too slow if the number of rectangles `N` were significantly larger (e.g., > 10^5).
### Explanation
The most efficient way to solve this problem is to realize that we only need to consider pairs of rectangles. The intersection of three or more rectangles will always be a sub-region of the intersection of any two of those rectangles. Therefore, it cannot contain a larger square.

The algorithm is as follows:

1.  Initialize a variable, `maxSide`, to 0. This will store the side length of the largest square found.
2.  Iterate through all unique pairs of rectangles. A common way to do this is with a nested loop structure where the outer loop variable `i` goes from `0` to `n-2` and the inner loop variable `j` goes from `i+1` to `n-1`.
3.  For each pair of rectangles, `rect_i` and `rect_j`, calculate their intersection. The intersection is also a rectangle whose boundaries are determined by the maximum of the bottom-left coordinates and the minimum of the top-right coordinates.
4.  If the calculated intersection has a positive width and height, it's a valid overlapping region. The side length of the largest square that can be inscribed in this intersection rectangle is the minimum of its width and height.
5.  Compare this side length with `maxSide` and update `maxSide` if the new side is larger.
6.  After checking all pairs, `maxSide` will hold the maximum possible side length. The result is the area, calculated as `(long)maxSide * maxSide` to prevent potential integer overflow since coordinates can be large.

```java
class Solution {
    public long largestSquareArea(int[][] bottomLeft, int[][] topRight) {
        int n = bottomLeft.length;
        long maxSide = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Calculate the intersection of rectangle i and rectangle j.
                // Bottom-left corner of the intersection
                long intersectX1 = Math.max(bottomLeft[i][0], bottomLeft[j][0]);
                long intersectY1 = Math.max(bottomLeft[i][1], bottomLeft[j][1]);

                // Top-right corner of the intersection
                long intersectX2 = Math.min(topRight[i][0], topRight[j][0]);
                long intersectY2 = Math.min(topRight[i][1], topRight[j][1]);

                // Check if there is a valid intersection
                if (intersectX2 > intersectX1 && intersectY2 > intersectY1) {
                    // The side of the largest square in the intersection is the minimum of its width and height.
                    long side = Math.min(intersectX2 - intersectX1, intersectY2 - intersectY1);
                    // Update the maximum side found so far.
                    maxSide = Math.max(maxSide, side);
                }
            }
        }

        // The result is the area of the square with the maximum side.
        return maxSide * maxSide;
    }
}
```
### Algorithm
*   Initialize a variable `maxSide` to 0 to keep track of the maximum possible side of a square.
*   Iterate through each unique pair of rectangles using two nested loops. Let the outer loop run for `i` from `0` to `n-1` and the inner loop for `j` from `i+1` to `n-1`.
*   For each pair of rectangles `i` and `j`, calculate the coordinates of their intersection.
    *   `intersectX1 = max(bottomLeft[i][0], bottomLeft[j][0])`
    *   `intersectY1 = max(bottomLeft[i][1], bottomLeft[j][1])`
    *   `intersectX2 = min(topRight[i][0], topRight[j][0])`
    *   `intersectY2 = min(topRight[i][1], topRight[j][1])`
*   Check if the intersection is a valid rectangle (i.e., if `intersectX2 > intersectX1` and `intersectY2 > intersectY1`).
*   If a valid intersection exists, calculate the side length of the largest square that can fit inside it: `side = min(intersectX2 - intersectX1, intersectY2 - intersectY1)`.
*   Update `maxSide` with the maximum value found so far: `maxSide = max(maxSide, side)`.
*   After iterating through all pairs, the maximum area is `(long)maxSide * maxSide`. Return this value.

# Solutions
### Java

```java
class Solution {
public
  long largestSquareArea(int[][] bottomLeft, int[][] topRight) {
    long ans = 0;
    for (int i = 0; i < bottomLeft.length; ++i) {
      int x1 = bottomLeft[i][0], y1 = bottomLeft[i][1];
      int x2 = topRight[i][0], y2 = topRight[i][1];
      for (int j = i + 1; j < bottomLeft.length; ++j) {
        int x3 = bottomLeft[j][0], y3 = bottomLeft[j][1];
        int x4 = topRight[j][0], y4 = topRight[j][1];
        int w = Math.min(x2, x4) - Math.max(x1, x3);
        int h = Math.min(y2, y4) - Math.max(y1, y3);
        int e = Math.min(w, h);
        if (e > 0) {
          ans = Math.max(ans, 1L * e * e);
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long largestSquareArea(vector<vector<int>> &bottomLeft,
                              vector<vector<int>> &topRight) {
    long long ans = 0;
    for (int i = 0; i < bottomLeft.size(); ++i) {
      int x1 = bottomLeft[i][0], y1 = bottomLeft[i][1];
      int x2 = topRight[i][0], y2 = topRight[i][1];
      for (int j = i + 1; j < bottomLeft.size(); ++j) {
        int x3 = bottomLeft[j][0], y3 = bottomLeft[j][1];
        int x4 = topRight[j][0], y4 = topRight[j][1];
        int w = min(x2, x4) - max(x1, x3);
        int h = min(y2, y4) - max(y1, y3);
        int e = min(w, h);
        if (e > 0) {
          ans = max(ans, 1LL * e * e);
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def largestSquareArea(self, bottomLeft: List[List[int]], topRight: List[List[int]]) -> int: ans = 0 for ((x1, y1), (x2, y2)), ((x3, y3), (x4, y4)) in combinations(zip(bottomLeft, topRight), 2): w = min(x2, x4) - max(x1, x3) h = min(y2, y4) - max(y1, y3) e = min(w, h) if e > 0: ans = max(ans, e * e) return ans

```