Number Of Rectangles That Can Form The Largest Square

Difficulty: Easy | Acceptance: 79.40% | Paid: No Topics: Array

You are given an array rectangles where rectangles[i] = [li, wi] represents the ith rectangle of length li and width wi.

You can cut the ith rectangle to form a square with a side length of k if both k <= li and k <= wi. For example, if you have a rectangle [4,6], you can cut it to get a square with a side length of at most 4.

Let maxLen be the side length of the largest square that you can obtain from any of the given rectangles.

Return the number of rectangles that can make a square with a side length of maxLen.

• Examples
• Constraints
• Single Pass
• Two Pass
• Functional Approach

Examples

Example 1:

Input: rectangles = [[5,8],[3,9],[5,12],[16,5]]
Output: 3
Explanation: The largest square you can make from each rectangle is of length [5,3,5,5].
The largest possible square is of length 5, and you can form it in 3 ways.

Example 2:

Input: rectangles = [[2,3],[3,7],[4,3],[4,4]]
Output: 1
Explanation: The largest square you can make from each rectangle is of length [2,3,3,4].
The largest possible square is of length 4, and you can form it in 1 way.

Constraints

- 1 <= rectangles.length <= 1000
- rectangles[i].length == 2
- 1 <= li, wi <= 10^9
- li != wi

Single Pass

Intuition Track the maximum square side and count rectangles that achieve it in a single iteration, updating both values as we go.

Steps

• Initialize max_side to 0 and count to 0
• For each rectangle, compute the minimum of length and width (max square side)
• If this side exceeds max_side, update max_side and reset count to 1
• If this side equals max_side, increment count
• Return the final count

class Solution:
    def countGoodRectangles(self, rectangles: List[List[int]]) -> int:
        max_side = 0
        count = 0
        for rect in rectangles:
            side = min(rect[0], rect[1])
            if side > max_side:
                max_side = side
                count = 1
            elif side == max_side:
                count += 1
        return count

Complexity

• Time: O(n) where n is the number of rectangles
• Space: O(1)
• Notes: Most efficient approach with minimal memory usage

Two Pass

Intuition First find the maximum square side across all rectangles, then count how many rectangles achieve this maximum.

Steps

• First pass: iterate through rectangles to find the maximum square side
• Second pass: count rectangles whose min dimension equals the maximum
• Return the count

class Solution:
    def countGoodRectangles(self, rectangles: List[List[int]]) -> int:
        max_side = 0
        for rect in rectangles:
            max_side = max(max_side, min(rect[0], rect[1]))
        
        count = 0
        for rect in rectangles:
            if min(rect[0], rect[1]) == max_side:
                count += 1
        
        return count

Complexity

• Time: O(n) where n is the number of rectangles
• Space: O(1)
• Notes: Slightly less efficient than single pass due to two iterations

Functional Approach

Intuition Use functional programming constructs to transform rectangles into their square sides, then find max and count occurrences.

Steps

• Map each rectangle to its minimum dimension (max square side)
• Find the maximum value from the mapped array
• Count occurrences of the maximum value
• Return the count

class Solution:
    def countGoodRectangles(self, rectangles: List[List[int]]) -> int:
        sides = [min(rect[0], rect[1]) for rect in rectangles]
        max_side = max(sides)
        return sides.count(max_side)

Complexity

• Time: O(n) where n is the number of rectangles
• Space: O(n) for storing the sides array
• Notes: More readable but uses extra memory for the intermediate array