Number Of Rectangles That Can Form The Largest Square


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 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.

Example 1:
Input: rectangles = [[5,8],[3,9],[5,12],[16,5]]
Output: 3
Explanation: The largest squares you can get from each rectangle are of lengths [5,3,5,5].
The largest possible square is of length 5, and you can get it out of 3 rectangles.

Example 2:
Input: rectangles = [[2,3],[3,7],[4,3],[3,7]]
Output: 3

Constraints:
1 <= rectangles.length <= 1000
rectangles[i].length == 2
1 <= li, wi <= 109
li != wi

Hints
1. What is the length of the largest square the can be cut out of some rectangle? It’ll be equal to min(rectangle.length, rectangle.width). Replace each rectangle with this value.
2. Calculate maxSize by iterating over the given rectangles and maximizing the answer with their values denoted in the first hint.
3. Then iterate again on the rectangles and calculate the number whose values = maxSize.

Algorithm to Number Of Rectangles That Can Form The Largest Square

First, we need to go through all rectangles, to find out the maxLength of all smaller sides. Then, we can go through all rectangles again to find out if smaller side is bigger or equal than the maxLength.

The complexity is O(N).

1
2
3
4
5
6
7
8
9
10
class Solution:
    def countGoodRectangles(self, rectangles: List[List[int]]) -> int:
        maxLength = 0
        for a, b in rectangles:
            maxLength = max(maxLength, min(a, b))
        ans = 0
        for a, b in rectangles:
            if min(a, b) >= maxLength:
                ans += 1
        return ans
class Solution:
    def countGoodRectangles(self, rectangles: List[List[int]]) -> int:
        maxLength = 0
        for a, b in rectangles:
            maxLength = max(maxLength, min(a, b))
        ans = 0
        for a, b in rectangles:
            if min(a, b) >= maxLength:
                ans += 1
        return ans

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
403 words
Last Post: Teaching Kids Programming - Re-implement the enumerate in Python using yield in a Generator
Next Post: Depth First Search Algorithm to Compute the Longest Tree Sum Path From Root to Leaf

The Permanent URL is: Number Of Rectangles That Can Form The Largest Square

Leave a Reply