1725. Number Of Rectangles That Can Form The Largest Square #

Problem #

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 <= 10^9
• li != wi

Problem Summary #

You are given an array rectangles, where rectangles[i] = [li, wi] represents the length li and width wi of the ith rectangle. If there exists k such that both k <= li and k <= wi, then the ith rectangle can be cut into a square with side length k. For example, the rectangle [4,6] can be cut into a square with a maximum side length of 4. Let maxLen be the side length of the largest square that can be obtained by cutting the rectangle array rectangles. Return the number of rectangles that can cut out a square with side length maxLen.

Solution Approach #

• Easy problem. Scan each rectangle in the array, first find the shorter side and use it as the side length of the square. During the scan, dynamically update the maximum square side length and accumulate the count. After one pass through the loop, output the final count.

Code #

package leetcode

func countGoodRectangles(rectangles [][]int) int {
	minLength, count := 0, 0
	for i, _ := range rectangles {
		minSide := 0
		if rectangles[i][0] <= rectangles[i][1] {
			minSide = rectangles[i][0]
		} else {
			minSide = rectangles[i][1]
		}
		if minSide > minLength {
			minLength = minSide
			count = 1
		} else if minSide == minLength {
			count++
		}
	}
	return count
}