Problem Description

You are given n rectangles on a 2D plane, where all rectangle edges are parallel to either the x-axis or y-axis. Each rectangle is defined by two points:

• bottomLeft[i] = [a_i, b_i] represents the bottom-left corner coordinates of the i-th rectangle
• topRight[i] = [c_i, d_i] represents the top-right corner coordinates of the i-th rectangle

Your task is to find the maximum area of a square that can fit inside the overlapping region where at least two rectangles intersect.

The key requirements are:

• The square must be completely contained within the intersection area of at least two rectangles
• You need to return the area of the largest such square
• If no two rectangles intersect (meaning no valid square can exist), return 0

For example, if two rectangles overlap and their intersection forms a region with width w and height h, the largest square that can fit in this intersection would have a side length of min(w, h), giving an area of min(w, h)².

The solution involves checking all possible pairs of rectangles, calculating their intersection (if it exists), determining the maximum square that fits in each intersection, and returning the largest area found across all valid intersections.

Intuition

Since we need to find a square that fits inside the intersection of at least two rectangles, we need to first understand how to find intersections between rectangles.

When two rectangles intersect, their intersection forms another rectangle (or nothing if they don't overlap). To find this intersection rectangle, we can observe that:

• The left boundary of the intersection is the rightmost of the two left boundaries: max(x1, x3)
• The bottom boundary of the intersection is the topmost of the two bottom boundaries: max(y1, y3)
• The right boundary of the intersection is the leftmost of the two right boundaries: min(x2, x4)
• The top boundary of the intersection is the bottommost of the two top boundaries: min(y2, y4)

This gives us the intersection rectangle's width as w = min(x2, x4) - max(x1, x3) and height as h = min(y2, y4) - max(y1, y3).

Now, since we need to fit a square inside this intersection rectangle, the largest square possible would have a side length equal to the smaller dimension of the rectangle. This is because a square needs equal width and height, so we're limited by whichever dimension is smaller: side_length = min(w, h).

If either w or h is negative or zero, it means the rectangles don't actually intersect, so no square can be formed.

Since we want the maximum area across all possible intersections, we need to check every pair of rectangles. With n rectangles, there are C(n, 2) pairs to check. For each valid intersection, we calculate the square area as min(w, h)² and keep track of the maximum area found.

This brute force approach works well because we must examine all possible rectangle pairs to ensure we don't miss the optimal intersection that yields the largest square.

Learn more about Math patterns.

Solution Approach

The implementation uses a straightforward enumeration approach to check all possible pairs of rectangles:

1. Generate All Rectangle Pairs: We use Python's combinations function along with zip to create pairs of rectangles. The zip(bottomLeft, topRight) combines corresponding bottom-left and top-right coordinates for each rectangle, and combinations(..., 2) generates all possible pairs.

2. For Each Pair of Rectangles, we extract the coordinates:

   • Rectangle 1: bottom-left (x1, y1) and top-right (x2, y2)
   • Rectangle 2: bottom-left (x3, y3) and top-right (x4, y4)

3. Calculate Intersection Dimensions:

   • Width of intersection: w = min(x2, x4) - max(x1, x3)
     • The rightmost left edge is max(x1, x3)
     • The leftmost right edge is min(x2, x4)
     • The difference gives us the width
   • Height of intersection: h = min(y2, y4) - max(y1, y3)
     • The topmost bottom edge is max(y1, y3)
     • The bottommost top edge is min(y2, y4)
     • The difference gives us the height

4. Determine Maximum Square Size:

   • The side length of the largest square that fits in the intersection is e = min(w, h)
   • We take the minimum because a square needs equal dimensions

5. Check Validity and Update Answer:

   • If e > 0, the rectangles actually intersect and we can form a square
   • Calculate the area as e * e
   • Update ans with the maximum area found so far using ans = max(ans, e * e)

6. Return Result: After checking all pairs, return the maximum square area found. If no valid intersections exist, the answer remains 0.

The time complexity is O(n²) where n is the number of rectangles, as we check all possible pairs. The space complexity is O(1) as we only use a constant amount of extra space for variables.

Example Walkthrough

Let's walk through a concrete example with 3 rectangles to illustrate the solution approach:

Input:

• Rectangle 1: bottomLeft = [1, 1], topRight = [4, 4]
• Rectangle 2: bottomLeft = [2, 2], topRight = [5, 5]
• Rectangle 3: bottomLeft = [6, 6], topRight = [8, 8]

Step 1: Generate all pairs We need to check 3 pairs: (Rect1, Rect2), (Rect1, Rect3), (Rect2, Rect3)

Step 2: Check Pair (Rectangle 1, Rectangle 2)

• Rectangle 1: (x1=1, y1=1) to (x2=4, y2=4)
• Rectangle 2: (x3=2, y3=2) to (x4=5, y4=5)

Calculate intersection:

• Width: w = min(4, 5) - max(1, 2) = 4 - 2 = 2
• Height: h = min(4, 5) - max(1, 2) = 4 - 2 = 2

Maximum square side: e = min(2, 2) = 2 Square area = 2 × 2 = 4

Step 3: Check Pair (Rectangle 1, Rectangle 3)

• Rectangle 1: (x1=1, y1=1) to (x2=4, y2=4)
• Rectangle 3: (x3=6, y3=6) to (x4=8, y4=8)

Calculate intersection:

• Width: w = min(4, 8) - max(1, 6) = 4 - 6 = -2
• Height: h = min(4, 8) - max(1, 6) = 4 - 6 = -2

Since w < 0, these rectangles don't intersect. No square possible.

Step 4: Check Pair (Rectangle 2, Rectangle 3)

• Rectangle 2: (x1=2, y1=2) to (x2=5, y2=5)
• Rectangle 3: (x3=6, y3=6) to (x4=8, y4=8)

Calculate intersection:

• Width: w = min(5, 8) - max(2, 6) = 5 - 6 = -1
• Height: h = min(5, 8) - max(2, 6) = 5 - 6 = -1

Since w < 0, these rectangles don't intersect. No square possible.

Step 5: Return maximum area The maximum square area found across all valid intersections is 4.

This example shows how the algorithm systematically checks each pair, calculates intersection dimensions, and tracks the maximum square area that can fit in any intersection.

Solution Implementation

Time and Space Complexity

The time complexity is O(n^2), where n is the number of rectangles. This is because the combinations(zip(bottomLeft, topRight), 2) generates all possible pairs of rectangles, which results in C(n, 2) = n * (n-1) / 2 pairs. For each pair, the algorithm performs constant time operations (calculating the intersection dimensions and updating the maximum area), so the overall time complexity is O(n^2).

The space complexity is O(1). The algorithm only uses a constant amount of extra space for variables ans, w, h, and e, regardless of the input size. The combinations function generates pairs on-the-fly as an iterator without storing all pairs in memory at once, so it doesn't contribute to the space complexity beyond the constant space needed for iteration state.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Intersection Calculation

A common mistake is incorrectly determining whether two rectangles actually intersect. Developers often forget that rectangles don't intersect when:

• The rightmost left edge is greater than or equal to the leftmost right edge
• The topmost bottom edge is greater than or equal to the bottommost top edge

Incorrect approach:

# Wrong: Assumes intersection exists without checking
intersection_width = min(x2, x4) - max(x1, x3)
intersection_height = min(y2, y4) - max(y1, y3)
square_area = min(intersection_width, intersection_height) ** 2

Correct approach:

# Right: Checks if dimensions are positive before using them
intersection_width = min(x2, x4) - max(x1, x3)
intersection_height = min(y2, y4) - max(y1, y3)
if intersection_width > 0 and intersection_height > 0:
    square_area = min(intersection_width, intersection_height) ** 2

2. Edge Case: Touching Rectangles

Rectangles that share only an edge or corner (but don't overlap in area) should not be considered as intersecting. The intersection width or height would be exactly 0 in these cases.

Problem scenario:

• Rectangle 1: bottomLeft = [0, 0], topRight = [2, 2]
• Rectangle 2: bottomLeft = [2, 0], topRight = [4, 2]
• These rectangles touch at x = 2 but don't overlap

The code correctly handles this by checking if max_square_side > 0, which ensures we only consider rectangles with positive overlap area.

3. Integer Overflow in Large Coordinates

When dealing with very large coordinate values, calculating the square area might cause integer overflow in some languages. While Python handles arbitrarily large integers, this could be an issue in languages like Java or C++.

Solution for other languages:

# Use long long in C++ or long in Java
# Or check for overflow before multiplication
if max_square_side > sqrt(MAX_INT):
    return MAX_INT
square_area = max_square_side * max_square_side

4. Misunderstanding the Problem Requirements

Some developers might think they need to find:

• The union of all rectangles (wrong)
• The intersection of ALL rectangles (wrong)
• A square that fits in ANY single rectangle (wrong)

The correct requirement is finding the largest square within the intersection of ANY TWO rectangles, which is why we use combinations(rectangles, 2).