3047. Find the Largest Area of Square Inside Two Rectangles LeetCode Solution

In this guide, you will get 3047. Find the Largest Area of Square Inside Two Rectangles LeetCode Solution with the best time and space complexity. The solution to Find the Largest Area of Square Inside Two Rectangles problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Find the Largest Area of Square Inside Two Rectangles solution in C++
4. Find the Largest Area of Square Inside Two Rectangles solution in Java
5. Find the Largest Area of Square Inside Two Rectangles solution in Python
6. Additional Resources

Problem Statement of Find the Largest Area of Square Inside Two Rectangles

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]

Complexity Analysis

• Time Complexity: O(n^2)
• Space Complexity: O(1)

3047. Find the Largest Area of Square Inside Two Rectangles LeetCode Solution in C++

class Solution {
 public:
  long long largestSquareArea(vector<vector<int>>& bottomLeft,
                              vector<vector<int>>& topRight) {
    int minSide = 0;

    for (int i = 0; i < bottomLeft.size(); ++i)
      for (int j = i + 1; j < bottomLeft.size(); ++j) {
        const int ax1 = bottomLeft[i][0];
        const int ay1 = bottomLeft[i][1];
        const int ax2 = topRight[i][0];
        const int ay2 = topRight[i][1];
        const int bx1 = bottomLeft[j][0];
        const int by1 = bottomLeft[j][1];
        const int bx2 = topRight[j][0];
        const int by2 = topRight[j][1];
        const int overlapX = min(ax2, bx2) - max(ax1, bx1);
        const int overlapY = min(ay2, by2) - max(ay1, by1);
        minSide = max(minSide, min(overlapX, overlapY));
      }

    return static_cast<long>(minSide) * minSide;
  }
};
/* code provided by PROGIEZ */

3047. Find the Largest Area of Square Inside Two Rectangles LeetCode Solution in Java

class Solution {
  public long largestSquareArea(int[][] bottomLeft, int[][] topRight) {
    int minSide = 0;

    for (int i = 0; i < bottomLeft.length; ++i)
      for (int j = i + 1; j < bottomLeft.length; ++j) {
        final int ax1 = bottomLeft[i][0];
        final int ay1 = bottomLeft[i][1];
        final int ax2 = topRight[i][0];
        final int ay2 = topRight[i][1];
        final int bx1 = bottomLeft[j][0];
        final int by1 = bottomLeft[j][1];
        final int bx2 = topRight[j][0];
        final int by2 = topRight[j][1];
        final int overlapX = Math.min(ax2, bx2) - Math.max(ax1, bx1);
        final int overlapY = Math.min(ay2, by2) - Math.max(ay1, by1);
        minSide = Math.max(minSide, Math.min(overlapX, overlapY));
      }

    return (long) minSide * minSide;
  }
}
// code provided by PROGIEZ

3047. Find the Largest Area of Square Inside Two Rectangles LeetCode Solution in Python

class Solution:
  def largestSquareArea(
      self,
      bottomLeft: list[list[int]],
      topRight: list[list[int]],
  ) -> int:
    minSide = 0

    for ((ax1, ay1), (ax2, ay2)), ((bx1, by1), (bx2, by2)) in (
            itertools.combinations(zip(bottomLeft, topRight), 2)):
      overlapX = min(ax2, bx2) - max(ax1, bx1)
      overlapY = min(ay2, by2) - max(ay1, by1)
      minSide = max(minSide, min(overlapX, overlapY))

    return minSide**2
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.