Find the Largest Area of Square Inside Two Rectangles
Source: leetcode
Difficulty: Medium
Tags: array, math, geometry

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.leetcode.com/uploads/2024/01/05/example12.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.leetcode.com/uploads/2024/07/15/diag.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.leetcode.com/uploads/2024/01/04/rectanglesexample2.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.leetcode.com/uploads/2024/01/04/rectanglesexample3.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]`




C++ solution:
struct Rectangle {
    int x;
    int y;
    int width;
    int height;
};

bool Compare(Rectangle &a, Rectangle &b) {
    return min(a.width, a.height) > min(b.width, b.height);
}

int Side(Rectangle* a, Rectangle* b) {
    int left = max(a->x, b->x);
    int right = min(a->x + a->width, b->x + b->width);
    int top = min(a->y, b->y);
    int bottom = max(a->y - a->height, b->y - b->height);
    int width = right - left;
    int height = top - bottom;
    return min(right - left, top - bottom);
}

class Solution {
public:
    long long largestSquareArea(vector<vector<int>>& bottom_left, vector<vector<int>>& top_right) {
        vector<Rectangle> rectangles;
        for (int a = 0; a < bottom_left.size(); ++a) {
            rectangles.push_back({
                bottom_left[a][0],
                top_right[a][1],
                top_right[a][0] - bottom_left[a][0],
                top_right[a][1] - bottom_left[a][1]
            });
        }
        sort(rectangles.begin(), rectangles.end(), Compare);
        int side = 0;
        for (int a = 0; a < rectangles.size(); ++a) {
            for (int b = a + 1; b < rectangles.size(); ++b) {
                if (min(rectangles[b].width, rectangles[b].height) <= side)
                    break;
                side = max(side, Side(&rectangles[a], &rectangles[b]));
            }
        }
        return static_cast<long long>(side) * static_cast<long long>(side);
    }
};

Go solution:
func largestSquareArea(bottomLeft [][]int, topRight [][]int) int64 {
    var maxArea int64 = 0
    for i := 0; i < len(bottomLeft); i++ {
        for j := i + 1; j < len(bottomLeft); j++ {
            blX := max(int64(bottomLeft[i][0]), int64(bottomLeft[j][0]))
            blY := max(int64(bottomLeft[i][1]), int64(bottomLeft[j][1]))
            trX := min(int64(topRight[i][0]), int64(topRight[j][0]))
            trY := min(int64(topRight[i][1]), int64(topRight[j][1]))

            if blX < trX && blY < trY {
                side := min(trX-blX, trY-blY)
                maxArea = max(maxArea, side*side)
            }
        }
    }

    return maxArea
}

Java solution:
class Solution {
    public long largestSquareArea(int[][] bottomLeft, int[][] topRight) {
        int ans = 0, n = bottomLeft.length;
        for (int i = 0; i < n; i++) {
            int[] firstRectBL = bottomLeft[i];
            int[] firstRectTR = topRight[i];
            for (int j = i + 1; j < n; j++) {
                int[] secondRectBL = bottomLeft[j];
                int[] secondRectTR = topRight[j];
                if (secondRectBL[0] >= firstRectTR[0] || secondRectTR[0] <= firstRectBL[0]) continue;
                if (secondRectTR[1] <= firstRectBL[1] || secondRectBL[1] >= firstRectTR[1]) continue;
                int pntAx = Math.max(firstRectBL[0], secondRectBL[0]);
                int pntAy = Math.max(firstRectBL[1], secondRectBL[1]);
                int pntBx = Math.min(firstRectTR[0], secondRectTR[0]);
                int pntBy = Math.min(firstRectTR[1], secondRectTR[1]);
                int sideA = pntBx - pntAx;
                int sideB = pntBy - pntAy;
                ans = Math.max(ans, Math.min(sideA, sideB));
            }
        }
        return (long) ans * ans;
    }
}

JavaScript solution:
/**
 * @param {number[][]} bottomLeft
 * @param {number[][]} topRight
 * @return {number}
 */
var largestSquareArea = function(bottomLeft, topRight) {
    let area=0;
    for(let i=0;i<bottomLeft.length;i++){
        for(let j=i+1;j<bottomLeft.length;j++){
            // finding the intersection points 
            let x1=Math.max(bottomLeft[i][0],bottomLeft[j][0]);
            let y1=Math.max(bottomLeft[i][1],bottomLeft[j][1]);
            let x2=Math.min(topRight[i][0],topRight[j][0]);
            let y2=Math.min(topRight[i][1],topRight[j][1]);
            
            if(x1<x2 && y1<y2){
                let side=Math.min(x2-x1,y2-y1);
                 area=Math.max(area,side*side);
            }
        }
    }
    return area;
};

Python solution:
class Solution:
    def largestSquareArea(self, bottomLeft: List[List[int]], topRight: List[List[int]]) -> int:
        result = 0 # store only one side, squared at the end

        rects = []
        for ( x1, y1 ), ( x2, y2 ) in zip(bottomLeft, topRight):
            rects.append(( x1, y1, x2, y2, min(x2 - x1, y2 - y1)))
        rects.sort()

        for i, ( x1, y1, x2, y2, s ) in enumerate(rects):
            # largest possible square
            if s <= result:
                continue

            for m1, n1, m2, n2, _ in rects[i + 1 :]:
                # no overlap or too small to produce a larger square
                if x2 - result <= m1:
                    break

                # extents
                x = min(x2, m2) - max(x1, m1)                
                y = min(y2, n2) - max(y1, n1)
                square = min(x, y)
                result = max(result, square)

        return result ** 2

Ruby solution:
# @param {Integer[][]} bottom_left
# @param {Integer[][]} top_right
# @return {Integer}
def largest_square_area(bottom_left, top_right)
  max_area = 0
  (0...bottom_left.length).each do |i|
    (i + 1...bottom_left.length).each do |j|
      x1 = [bottom_left[i][0], bottom_left[j][0]].max
      y1 = [bottom_left[i][1], bottom_left[j][1]].max
      x2 = [top_right[i][0], top_right[j][0]].min
      y2 = [top_right[i][1], top_right[j][1]].min
      side = [x2 - x1, y2 - y1].min
      if side > 0
        max_area = [max_area, side * side].max
      end
    end
  end
  max_area
end