Problem Description

You are given an array rectangles where each element rectangles[i] = [li, wi] represents a rectangle with length li and width wi.

From each rectangle, you can cut out a square. The maximum side length of the square you can cut from a rectangle is limited by the smaller dimension of that rectangle. Specifically, from a rectangle with dimensions [l, w], you can cut a square with side length k only if k ≤ l and k ≤ w. This means the maximum square you can cut has a side length of min(l, w).

For example, if you have a rectangle [4, 6], the largest square you can cut from it has a side length of 4 (the minimum of 4 and 6).

Your task is to:

1. Find the maximum side length (maxLen) among all possible squares that can be cut from all the given rectangles
2. Count how many rectangles can produce a square with this maximum side length

The function should return the count of rectangles that can make a square with side length equal to maxLen.

Example walkthrough:

• If rectangles = [[5,8], [3,9], [5,12], [16,5]]
• Rectangle [5,8] can make a square with max side length 5
• Rectangle [3,9] can make a square with max side length 3
• Rectangle [5,12] can make a square with max side length 5
• Rectangle [16,5] can make a square with max side length 5
• The maximum side length among all is 5, and three rectangles can produce this, so the answer is 3

Intuition

The key insight is that for each rectangle, the largest square we can cut from it is determined by its smaller dimension. If a rectangle has dimensions [l, w], then the maximum square side length is min(l, w) because the square must fit within both dimensions.

Once we understand this, the problem becomes straightforward: we need to find the maximum value among all these minimum dimensions, then count how many rectangles can produce this maximum value.

We can solve this efficiently in a single pass through the array. As we examine each rectangle:

• Calculate the maximum square side length for that rectangle: x = min(l, w)
• Compare this with our current maximum (mx):
  • If we find a larger value (x > mx), we've discovered a new maximum. Reset our count to 1 and update the maximum.
  • If we find an equal value (x == mx), we've found another rectangle that can produce the same maximum square. Increment our count.
  • If we find a smaller value (x < mx), we ignore it as it doesn't affect our answer.

This approach allows us to track both the maximum square side length and the count of rectangles that can achieve it in a single traversal, making it an O(n) solution with O(1) extra space.

The elegance of this solution lies in maintaining just two variables (mx for the maximum side length and ans for the count) and updating them appropriately as we scan through the rectangles once.

Solution Approach

The solution uses a single-pass algorithm with two tracking variables to solve the problem efficiently.

Implementation Details:

1. Initialize tracking variables:

   • ans = 0: Counts the number of rectangles that can produce the maximum square
   • mx = 0: Tracks the current maximum square side length found

2. Process each rectangle: For each rectangle [l, w] in the array:

   • Calculate the maximum square side length: x = min(l, w)
   • This represents the largest square that can be cut from this rectangle

3. Update the tracking variables based on comparison:

   • Case 1: Found a larger square (mx < x)
     • Update mx = x to record the new maximum
     • Reset ans = 1 since this is the first rectangle with this new maximum size
   • Case 2: Found an equal square (mx == x)
     • Increment ans += 1 since we found another rectangle that can produce the maximum square
   • Case 3: Found a smaller square (mx > x)
     • Do nothing (implicitly handled by not having an else clause)

4. Return the result: After processing all rectangles, ans contains the count of rectangles that can produce the maximum square side length.

Time Complexity: O(n) where n is the number of rectangles, as we traverse the array once.

Space Complexity: O(1) as we only use two variables regardless of input size.

The algorithm efficiently combines the search for the maximum value and counting occurrences of that maximum in a single pass, eliminating the need for a two-pass approach (first finding the maximum, then counting).

Example Walkthrough

Let's walk through a small example with rectangles = [[2,3], [3,7], [4,3], [3,3]]

Initial state:

• mx = 0 (maximum square side length found so far)
• ans = 0 (count of rectangles that can produce the maximum square)

Step 1: Process rectangle [2,3]

• Maximum square from this rectangle: x = min(2,3) = 2
• Compare with current maximum: mx = 0 < x = 2
• Since we found a larger square, update:
  • mx = 2 (new maximum)
  • ans = 1 (first rectangle with this size)

Step 2: Process rectangle [3,7]

• Maximum square from this rectangle: x = min(3,7) = 3
• Compare with current maximum: mx = 2 < x = 3
• Since we found an even larger square, update:
  • mx = 3 (new maximum)
  • ans = 1 (reset count for new maximum)

Step 3: Process rectangle [4,3]

• Maximum square from this rectangle: x = min(4,3) = 3
• Compare with current maximum: mx = 3 == x = 3
• Since this equals our current maximum, increment:
  • mx = 3 (unchanged)
  • ans = 2 (second rectangle with this size)

Step 4: Process rectangle [3,3]

• Maximum square from this rectangle: x = min(3,3) = 3
• Compare with current maximum: mx = 3 == x = 3
• Since this also equals our current maximum, increment:
  • mx = 3 (unchanged)
  • ans = 3 (third rectangle with this size)

Final Result: Return ans = 3

The maximum square side length is 3, and three rectangles ([3,7], [4,3], and [3,3]) can produce a square of this size.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array rectangles. The algorithm iterates through each rectangle exactly once, performing constant-time operations (finding minimum, comparison, and increment) for each element.

The space complexity is O(1). The algorithm only uses a fixed amount of extra space with variables ans, mx, x, l, and w, regardless of the input size. No additional data structures that grow with the input are created.

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

Common Pitfalls

Pitfall 1: Incorrectly Resetting the Counter

The Mistake: A common error is forgetting to reset the counter when finding a new maximum, leading to incorrect counting:

# INCORRECT implementation
def countGoodRectangles(self, rectangles: List[List[int]]) -> int:
    count = 0
    max_side = 0
  
    for length, width in rectangles:
        square_side = min(length, width)
      
        if square_side > max_side:
            # Forgot to reset count!
            max_side = square_side
        elif square_side == max_side:
            count += 1
  
    return count

This would accumulate counts from previous smaller maximums, giving wrong results.

The Fix: Always reset the counter to 1 when discovering a new maximum:

if square_side > max_side:
    count = 1  # Reset to 1, not 0
    max_side = square_side

Pitfall 2: Off-by-One Error in Counter Initialization

The Mistake: Starting with count = 1 or resetting to 0 instead of 1 when finding a new maximum:

# INCORRECT - resetting to 0
if square_side > max_side:
    count = 0  # Wrong! Should be 1
    max_side = square_side
elif square_side == max_side:
    count += 1

This misses counting the first rectangle that establishes the new maximum.

Pitfall 3: Using Max Instead of Min for Square Side

The Mistake: Using max(length, width) instead of min(length, width):

# INCORRECT
square_side = max(length, width)  # Wrong!

A square must fit within both dimensions, so we need the minimum, not maximum.

Pitfall 4: Handling Edge Cases Incorrectly

The Mistake: Not considering empty input or assuming all dimensions are positive:

def countGoodRectangles(self, rectangles: List[List[int]]) -> int:
    if not rectangles:  # Edge case handling
        return 0
  
    count = 0
    max_side = 0
  
    for length, width in rectangles:
        # Could add validation here if needed
        if length <= 0 or width <= 0:
            continue
        square_side = min(length, width)
        # ... rest of logic

Best Practice Solution: The correct approach maintains clear logic for all three cases:

def countGoodRectangles(self, rectangles: List[List[int]]) -> int:
    count = 0
    max_side = 0
  
    for length, width in rectangles:
        square_side = min(length, width)
      
        if square_side > max_side:
            count = 1  # Found new maximum, reset to 1
            max_side = square_side
        elif square_side == max_side:
            count += 1  # Found another with same max size
        # implicitly: if square_side < max_side, do nothing
  
    return count