Number Of Rectangles That Can Form The Largest Square
EasyPrompt
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 <= 1000rectangles[i].length == 21 <= li, wi <= 109li != wi
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves calculating the maximum possible square side for each rectangle, storing these side lengths in a list, sorting the list, and then counting the occurrences of the largest value.
Algorithm
- Create an empty list,
sideLengths. - Iterate through each
rectanglein the inputrectanglesarray. - For each
rectangle, calculateside = min(rectangle[0], rectangle[1]). - Add
sideto thesideLengthslist. - Sort the
sideLengthslist in descending order. - Get the
maxLenwhich is the first element of the sorted list. - Initialize a
countto 0. - Iterate through the
sideLengthslist. If an element is equal tomaxLen, incrementcount. If it's smaller, break the loop (since the list is sorted). - Return
count.
Walkthrough
The core idea is to first transform the problem from dealing with rectangles to dealing with a simple list of numbers. For each rectangle [l, w], the largest square that can be cut has a side length of min(l, w). We compute this value for every rectangle and store it in an auxiliary array.
Once we have this array of possible side lengths, we can sort it in descending order. The largest possible side length, maxLen, will be the first element of the sorted array.
Finally, we iterate through the sorted array to count how many times maxLen appears. This count is our final answer.
import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution { public int countGoodRectangles(int[][] rectangles) { List<Integer> sideLengths = new ArrayList<>(); for (int[] rect : rectangles) { sideLengths.add(Math.min(rect[0], rect[1])); } Collections.sort(sideLengths, Collections.reverseOrder()); if (sideLengths.isEmpty()) { return 0; } int maxLen = sideLengths.get(0); int count = 0; for (int side : sideLengths) { if (side == maxLen) { count++; } else { // Since the list is sorted, we can stop early break; } } return count; }}Complexity
Time
O(N log N), where N is the number of rectangles. The dominant operation is sorting the list of side lengths.
Space
O(N), as we need an auxiliary list to store the side length for each of the N rectangles.
Trade-offs
Pros
Conceptually simple and breaks the problem down into distinct, easy-to-understand steps (calculate, sort, count).
Cons
Requires extra space to store the side lengths.
The sorting step makes it less efficient than linear time approaches, especially for large inputs.
Solutions
Solution
class Solution { public int countGoodRectangles ( int [][] rectangles ) { int ans = 0 , mx = 0 ; for ( var e : rectangles ) { int x = Math . min ( e [ 0 ], e [ 1 ]); if ( mx < x ) { mx = x ; ans = 1 ; } else if ( mx == x ) { ++ ans ; } } return ans ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.