Find the Largest Area of Square Inside Two Rectangles Interview Question for Google

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 i<sup>th</sup> 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.

For example:

bottomLeft = [[1,1],[2,2],[3,1]], topRight = [[3,3],[4,4],[6,6]] Output: 1 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.

bottomLeft = [[1,1],[1,3],[1,5]], topRight = [[5,5],[5,7],[5,9]] Output: 4 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.

bottomLeft = [[1,1],[2,2],[1,2]], topRight = [[3,3],[4,4],[3,4]] Output: 1 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.

bottomLeft = [[1,1],[3,3],[3,1]], topRight = [[2,2],[4,4],[4,2]] Output: 0 No pair of rectangles intersect, hence, the answer is 0.

What is the most efficient algorithm to solve this problem?

def max_square_area(bottomLeft, topRight):
    n = len(bottomLeft)
    max_area = 0

    for i in range(n):
        for j in range(i + 1, n):
            # Find the intersection rectangle
            x1 = max(bottomLeft[i][0], bottomLeft[j][0])
            y1 = max(bottomLeft[i][1], bottomLeft[j][1])
            x2 = min(topRight[i][0], topRight[j][0])
            y2 = min(topRight[i][1], topRight[j][1])

            # If there is an intersection
            if x1 < x2 and y1 < y2:
                # Find the maximum possible side length of a square
                side = min(x2 - x1, y2 - y1)
                max_area = max(max_area, side * side)

    return max_area

# Example 1
bottomLeft1 = [[1,1],[2,2],[3,1]]
topRight1 = [[3,3],[4,4],[6,6]]
print(f"Example 1: {max_square_area(bottomLeft1, topRight1)}") # Output: 1

# Example 2
bottomLeft2 = [[1,1],[1,3],[1,5]]
topRight2 = [[5,5],[5,7],[5,9]]
print(f"Example 2: {max_square_area(bottomLeft2, topRight2)}") # Output: 4

# Example 3
bottomLeft3 = [[1,1],[2,2],[1,2]]
topRight3 = [[3,3],[4,4],[3,4]]
print(f"Example 3: {max_square_area(bottomLeft3, topRight3)}") # Output: 1

# Example 4
bottomLeft4 = [[1,1],[3,3],[3,1]]
topRight4 = [[2,2],[4,4],[4,2]]
print(f"Example 4: {max_square_area(bottomLeft4, topRight4)}") # Output: 0

Brute Force Solution

The brute force solution iterates through all pairs of rectangles, finds the intersection of each pair, and determines the maximum square area that can fit within that intersection. This involves calculating the overlapping region's coordinates and then finding the largest possible square side length.

Optimal Solution

The provided solution is already optimized for the constraints given. Since we need to check every pair of rectangles to find the intersection, we cannot avoid the nested loops. Thus the given solution is optimal.

Big(O) Run-time Analysis

The time complexity is O(n^2), where n is the number of rectangles. This is because we have a nested loop that iterates through all possible pairs of rectangles. For each pair, we perform a constant amount of work to calculate the intersection and determine the maximum square area.

Big(O) Space Usage Analysis

The space complexity is O(1) because we only use a few variables to store the intersection coordinates and the maximum area found so far. We do not use any additional data structures that scale with the input size.

Edge Cases

No Intersection: If no two rectangles intersect, the function should return 0. This is handled correctly because if x1 >= x2 or y1 >= y2, the intersection is considered empty, and the max_area is not updated.
Perfect Overlap: If two rectangles are perfectly overlapping, the intersection is the same as the rectangles themselves. The algorithm will correctly calculate the maximum square area that can fit inside.
One Rectangle Inside Another: If one rectangle is completely inside another, the intersection is the inner rectangle. The algorithm correctly calculates the maximum square area in this case as well.
Large Coordinates: The coordinates can be large (up to 10^7). The algorithm can handle these large values because it only performs basic arithmetic operations (min, max, subtraction) on them. The int type in Python can handle such large numbers without overflow.
Negative Coordinates (Not Allowed): The problem statement says that coordinates are between 1 and 10^7. So no negative coordinates.
Zero Area Rectangles (Not Allowed): The problem statement says that bottomLeft[i][0] < topRight[i][0] and bottomLeft[i][1] < topRight[i][1]. So no zero area rectangles.
Number of rectangles is less than 2: The problem states that n >= 2, so we don't need to handle the case of having less than 2 rectangles.