We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Largest Area of Square Inside Two Rectangles

Number: 3325

Difficulty: Medium

Paid? No

Companies: Google, Cisco

Problem Description

Given n rectangles in a 2D plane (with edges parallel to the axes), each defined by its bottom-left and top-right coordinates, find the maximum area of a square that can completely fit inside the intersection region of at least two rectangles. If no two rectangles intersect (or no square can fit in any intersection), return 0.

Key Insights

  • The intersection of two rectangles (if it exists) is itself a rectangle with:
    • bottom-left coordinates: (max(a₁, a₂), max(b₁, b₂))
    • top-right coordinates: (min(c₁, c₂), min(d₁, d₂))
  • The valid intersection exists only if min(c₁, c₂) > max(a₁, a₂) and min(d₁, d₂) > max(b₁, b₂).
  • The side length of the largest square that can fit inside the intersected rectangle is the minimum of its width and height.
  • A brute-force solution checking all pairs of rectangles will run in O(n²) time, which is acceptable given n ≤ 10³.

Space and Time Complexity

Time Complexity: O(n²) – We check every pair of rectangles. Space Complexity: O(1) – Only a few extra variables are used, aside from the input.

Solution

The approach is to iterate over each unique pair of rectangles and:

  1. Compute the intersection rectangle by taking the maximum of the bottom-left coordinates and the minimum of the top-right coordinates.
  2. If an intersection exists (i.e., the computed width and height are positive), determine the side length of the square that can fit by taking the minimum of the width and height.
  3. Update the maximum square area encountered.
  4. Return the result (maximum area, which is side²) or 0 if no valid intersection exists.

The solution uses straightforward arithmetic operations and simple comparisons. No complex data structures are needed.

Code Solutions

# Python solution for finding the largest area of square inside two rectangle intersections

def largestSquareArea(bottomLeft, topRight):
    # Initialize maximum square side to 0
    max_side = 0
    n = len(bottomLeft)
    # Iterate over all pairs of rectangles
    for i in range(n):
        for j in range(i + 1, n):
            # For rectangle i and rectangle j, compute the intersection coordinates
            intersect_bottom_left_x = max(bottomLeft[i][0], bottomLeft[j][0])
            intersect_bottom_left_y = max(bottomLeft[i][1], bottomLeft[j][1])
            intersect_top_right_x = min(topRight[i][0], topRight[j][0])
            intersect_top_right_y = min(topRight[i][1], topRight[j][1])
            
            # Check if the intersection is valid (non-zero width and height)
            if intersect_top_right_x > intersect_bottom_left_x and intersect_top_right_y > intersect_bottom_left_y:
                # Compute the width and height of the intersection rectangle
                width = intersect_top_right_x - intersect_bottom_left_x
                height = intersect_top_right_y - intersect_bottom_left_y
                # The largest square's side that can fit is the minimum of these two
                square_side = min(width, height)
                # Update maximum side length if current one is larger
                max_side = max(max_side, square_side)
    
    # Return the area of the square with the maximum side length found
    return max_side ** 2

# Example usage:
print(largestSquareArea([[1,1],[2,2],[3,1]], [[3,3],[4,4],[6,6]]))  # Output: 1
← Back to All Questions