Number Of Rectangles That Can Form The Largest Square

Problem Description

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. Let maxLen be the side length of the largest square 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.

Key Insights

• The largest square that can be formed from a rectangle is determined by the shorter side of the rectangle.
• We need to find the maximum value of these shorter sides across all rectangles.
• After determining the maximum square size, we count how many rectangles can produce a square of that size.

Space and Time Complexity

Time Complexity: O(n), where n is the number of rectangles, since we iterate through the list to find the max square size and count. Space Complexity: O(1), as we only use a few additional variables.

Solution

To solve this problem, we can use a simple linear scan through the list of rectangles:

1. For each rectangle, calculate the minimum of its length and width, which gives the maximum square size that can be formed from that rectangle.
2. Keep track of the largest square size found during this scan.
3. After identifying the largest square size, perform another scan to count how many rectangles can form a square of that size. This approach uses an array for the input and a couple of variables to track the maximum size and count, ensuring an efficient solution.

Code Solutions