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

Number Of Rectangles That Can Form The Largest Square

Number: 1843

Difficulty: Easy

Paid? No

Companies: AllinCall

Problem Description

Given an array of rectangles where each rectangle is represented by its length and width, determine the number of rectangles that can form the largest square. The side length of the square that can be cut out of a rectangle is limited by the smaller of the rectangle’s two dimensions. First, find the maximum square side length possible from all rectangles, then count how many rectangles can produce a square of that side length.

Key Insights

  • The largest square from a rectangle is determined by the minimum of its two dimensions.
  • The maximum possible square side (maxLen) is the largest among these minimum values from each rectangle.
  • Count how many rectangles have this maximum square side.
  • The solution requires a simple linear scan through the array with constant extra space.

Space and Time Complexity

Time Complexity: O(n), where n is the number of rectangles. Space Complexity: O(1) extra space.

Solution

The approach involves iterating over the list of rectangles to determine the maximum square side that can be obtained (by taking the minimum of each rectangle's dimensions). Once the maximum side (maxLen) is identified, iterate again (or count simultaneously) to count how many rectangles have that square side. This leverages simple arithmetic and comparisons in a single or double pass over the array, ensuring an efficient solution.

Code Solutions

# Function to count rectangles that can form the largest square
def count_good_rectangles(rectangles):
    max_square_side = 0
    # Find the max possible square side from each rectangle
    for length, width in rectangles:
        side = min(length, width)  # square side is limited by the smaller dimension
        if side > max_square_side:
            max_square_side = side  # update max square side if current is larger
    # Count rectangles that can form a square with side equal to max_square_side
    count = 0
    for length, width in rectangles:
        if min(length, width) == max_square_side:
            count += 1
    return count

# Example usage:
rectangles = [[5,8], [3,9], [5,12], [16,5]]
print(count_good_rectangles(rectangles))  # Expected output: 3
← Back to All Questions