Number Of Rectangles That Can Form The Largest Square - Leetcode Solution

Problem statement:

Given a list of rectangles, find the number of rectangles that can form the largest square.

Solution:

To solve this problem, we need to understand certain properties of rectangles and squares. A square is a special type of rectangle in which all sides are of equal length. Therefore, if we can find the side length of the largest square that can be formed, we can then calculate the number of rectangles that can form that square.

To find the side length of the largest square, we need to first find the minimum width and height of all the rectangles. This is because the side length of the square cannot exceed the smaller of the two dimensions.

Once we have the minimum dimension, we can then traverse the list of rectangles to count how many rectangles have the minimum dimension as either their width or height. This count represents the number of rectangles that can form the largest square.

Code:

Here is the Python implementation of the above approach:

class Solution:
    def countGoodRectangles(self, rectangles: List[List[int]]) -> int:
        min_dim = min(min(x) for x in rectangles)
        count = 0
        for r in rectangles:
            if r[0]>=min_dim and r[1]>=min_dim:
                count += 1
        return count

The above code first finds the minimum dimension (min_dim) using a nested list comprehension. It then initializes a count variable to zero. Finally, it iterates through the list of rectangles, checking whether each rectangle has the minimum dimension as either its width or height, and incrementing the count variable if this condition is met.

Time Complexity:

The time complexity of this approach is O(N), where N is the number of rectangles in the input list. This is because we only need to traverse the list once to find the count of rectangles that can form the largest square.

Space Complexity:

The space complexity of this approach is O(1), as we only need to store a constant amount of information (the minimum dimension and the count of rectangles that can form the largest square).

1