Problem Statement in English

You’re given two 2D integer arrays bl and tr representing the bottom-left and top-right coordinates of n rectangles respectively.

Return the area of the largest square that can fit inside any of the rectangles. If no square can fit inside any rectangle, return 0.

Approach

Just imagine that we have two rectangles. To find the overlapping area, we can determine the bottom-left and top-right coordinates of the overlapping rectangle.

This can be done by taking the maximum of the bottom-left coordinates and the minimum of the top-right coordinates of both rectangles.

If the resulting bottom-left coordinates are less than the top-right coordinates, it indicates an overlap.

Then we take the minimum of the width and height of the overlapping rectangle to determine the side length of the largest square that can fit within it.

Solution in Python


class Solution:
    def largestSquareArea(self, bl: List[List[int]], tr: List[List[int]]) -> int:
        s = 0
        n = len(bl)

        for i in range(n):
            for j in range(i + 1, n):
                bl_x = max(bl[i][0], bl[j][0])
                tr_x = min(tr[i][0], tr[j][0])
                bl_y = max(bl[i][1], bl[j][1])
                tr_y = min(tr[i][1], tr[j][1])

                if bl_x < tr_x and bl_y < tr_y:
                    length = min(tr_x - bl_x, tr_y - bl_y)
                    s = max(s, length)

        return s * s

Complexity

  • Time: $O(n^2)$
    Since we have a nested loop iterating through all pairs of rectangles, the time complexity is quadratic in relation to the number of rectangles, denoted as $n$.

  • Space: $O(1)$
    Since we are using only a constant amount of extra space for variables, the space complexity is constant.

Mistakes I Made

I had to look this up :(

And we are done.