Skip to content

Find the Largest Area of Square Inside Two Rectangles⚓︎

Link

Solution⚓︎

See reference (Chinese).

If rectangles intersect, then the intersection must be a rectangle. Find the lower-left and upper-right corners of this intersecting rectangle.

  • Lower-left horizontal coordinate: the maximum of the horizontal coordinates of the lower-left corners of the two rectangles.
  • Lower-left vertical coordinate: the maximum of the vertical coordinates of the lower-left corners of the two rectangles.
  • Upper right horizontal coordinate: the minimum value of the horizontal coordinate of the upper right corner of the two rectangles.
  • Upper right vertical coordinate: the minimum value of the vertical coordinate of the upper right corner of the two rectangles.

Knowing the coordinates, we can calculate the length and width of the rectangle, and take the minimum of the two as the length of the side of the square.

If the rectangles do not intersect, then the length and width are negative, judged before calculating the area.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    long long largestSquareArea(vector<vector<int>>& bottomLeft, vector<vector<int>>& topRight) {
        long long res = 0;

        for (int i = 0; i < bottomLeft.size(); i++) {
            auto& b1 = bottomLeft[i];
            auto& t1 = topRight[i];

            for (int j = i + 1; j < bottomLeft.size(); j++) {
                auto& b2 = bottomLeft[j];
                auto& t2 = topRight[j];

                int height = min(t1[1], t2[1]) - max(b1[1], b2[1]);
                int width = min(t1[0], t2[0]) - max(b1[0], b2[0]);

                int size = min(width, height);
                if (size > 0) {
                    res = max(res, static_cast<long long>(size) * size);
                }
            }
        }

        return res;
    }
};
  • Time complexity: \(O(n^2)\);
  • Space complexity: \(O(1)\).