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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Largest Area of Square Inside Two Rectangles

Difficulty: Medium

Problem Description

Given two 2D integer arrays bottomLeft and topRight representing n rectangles in a 2D plane, find the maximum area of a square that can fit inside the intersecting region of at least two rectangles. If no such square exists, return 0.

Key Insights

  • The intersection of two rectangles can be computed using their bottom-left and top-right coordinates.
  • The width and height of the intersection can be determined to find the largest square that can fit within it.
  • The maximum side length of the square is constrained by the smaller of the width and height of the intersection area.
  • It is important to check all pairs of rectangles to find the maximum square area.

Space and Time Complexity

Time Complexity: O(n^2) - We check each pair of rectangles, resulting in a quadratic time complexity. Space Complexity: O(1) - We use a constant amount of space for variables.

Solution

To solve the problem, we can iterate through each pair of rectangles and calculate their intersection's coordinates. For each intersection, we determine the width and height. The side length of the largest square that can fit in the intersection is the minimum of these two dimensions. We keep track of the maximum square area found during these iterations.

Code Solutions

def maxSquareArea(bottomLeft, topRight):
    max_area = 0
    
    n = len(bottomLeft)
    
    for i in range(n):
        for j in range(i + 1, n):
            # Calculate the intersection of rectangles i and j
            inter_bottom_left_x = max(bottomLeft[i][0], bottomLeft[j][0])
            inter_bottom_left_y = max(bottomLeft[i][1], bottomLeft[j][1])
            inter_top_right_x = min(topRight[i][0], topRight[j][0])
            inter_top_right_y = min(topRight[i][1], topRight[j][1])
            
            # Check if there is an intersection
            if inter_bottom_left_x < inter_top_right_x and inter_bottom_left_y < inter_top_right_y:
                # Calculate width and height of the intersection
                width = inter_top_right_x - inter_bottom_left_x
                height = inter_top_right_y - inter_bottom_left_y
                
                # The side length of the largest square that can fit is the minimum of width and height
                side_length = min(width, height)
                max_area = max(max_area, side_length * side_length)
    
    return max_area
← Back to All Questions