Number Of Rectangles That Can Form The Largest Square

The task requires determining the maximum possible square’s side length that can be formed from a set of given rectangles. Each rectangle can be cut down to a square with a side length equal to the smaller side of the rectangle. The function should return the number of rectangles that can make a square with this maximum possible side length.

You can solve this problem using the following steps:

1. Traverse each rectangle in the list, and for each rectangle, get the minimum of length and width, which would be the maximum possible side length of the square that can be cut from this rectangle.

2. Keep track of the maximum square side length obtained so far.

3. Count how many rectangles can form a square of this maximum side length.

Let’s translate these steps into Python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def countGoodRectangles(self, rectangles: List[List[int]]) -> int:
        # Initialize max_len to be the side length of square cut from first rectangle
        max_len = min(rectangles[0])
        # Initialize count to be 1, as we already considered first rectangle
        count = 1

        # Traverse from the second rectangle
        for i in range(1, len(rectangles)):
            # Calculate the side length of square that can be cut from current rectangle
            cur_len = min(rectangles[i])

            # If current length is greater than max_len
            if cur_len > max_len:
                # Update max_len and reset count to 1
                max_len = cur_len
                count = 1
            # If current length is equal to max_len
            elif cur_len == max_len:
                # Increment count
                count += 1

        # Return the count
        return count

The time complexity of the above solution is O(n), where n is the number of rectangles, since we traverse the list of rectangles once. The space complexity is O(1), as we only use a fixed amount of space to store the max_len and count.