Skip to content

3047. Find the Largest Area of Square Inside Two Rectangles

  • Time: $O(n^2)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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